NR 物理层编码 S2 - 汉明码

发布于：2022-12-19 ⋅ 阅读:(877) ⋅ 点赞:(0)

参考：

Neso Academy 《Hamming Code | Error detection》

7.线性分组码-汉明码-普洛西金界_哔哩哔哩_bilibili

目录:

定义
编码流程
汉明界
完备码
例题

一定义

如果线性分组码（n,k）满足码字长度为

$n=2^r-1$

监督位长度为 $r$

信息位长度为 $n-r$

则称这种码为汉明码.

能纠正一位误码

码率

$\eta=\frac{n-r}{n}=1-\frac{r}{n}$

固定码长n,要检测的最大位数为t

假设有1位误码,错误图样为 $c_n^1$

假设有2位误码,错误图样为 $c_n^2$

假设有t位误码,错误图样为 $c_n^t$

伴随式共有 $2^{r}$ 种,去除全0的，需要满足下面等式

$2^{r}-1\geq c_n^1+c_n^2+..c_{n}^{t}$

二编码流程

有三种方案：

主要分为如下三步：

3.1 确定校验位个数

一般已知k，根据下面公式来计算r

$n=2^r-1$

$k=2^r-1-r$

2.2 计算校验位置

汉明码是一种偶校验码，校验位必须在 $2^{i},i=0,1,..,r-1$ 位置上.

依然以上面为例,给定信息长度k=4,知道r=3, n=7

$P_1= C_1(i=0,2^0=1)$

$P_2= C_2(i=1,2^1=2)$

$P_3= C_4(i=2,2^2=4)$

2.3 用校验位的线性组合来表示信息位

$c_3[m_1],c_5[m_2],c_6[m_3],c_7[m_4]$ 存放信息位,

$c_1[p_1],c_2[p_2],c_4[p_3]$ 用于存放校验位

方案1

第一步：校验位的线性组合来生成和信息位的关系（编码矩阵G）



   $c_3=c_1+c_2=p_1+p_2$ ...1

   $c_5=c_1+c_4=p_1+p_3$ ....2

$c_6=c_2+c_4=p_2+p_3$ ...3

$c_7=c_1+c_2+c_4=p_1+p_2+p_3$ ...4

第二步: 把包含校验位的所有等式相加得到校验方程（校验矩阵H）

$p_1=c_3+c_5+c_7=m_1+m_2+m_4$ (等式1+等式2+等式4）

   $p_2=c_3+c_6+c_7=m_1+m_3+m_4$ (等式1+等式3+等式4）

$p_3=c_5+c_6+c_7=m_2+m_3+m_4$ （等式2+等式3+等式4）

方案2

通过校正子来生成

1 先写出校正子,当r=3时候,去除000,共有7种。

2 找出校正子每列中不为0的项,对应的码字加起来就得到一个校正等式

$c_1+c_3+c_5+c_7=0$ ,再找到码字中跟信息源以及监督元的映射关系得到

$P_1=m_1+m_2+m_4$

$p_2=m_1+m_3+m_4$ (同理）

$p_3=m_2+m_3+m_4$ (同理）

方案3：通过校验矩阵H，得到编码矩阵G

因为汉明码的纠正能力为1，所以最小码距为3，则奇偶校验部分

为 $c_3^2+c_3^3$ (利用后面3列的线性组合）

通过转置得到编码矩阵

我们通过 $c=uG$ ,其实现的就是下面功能

三汉明界

线性分组码（n,k）能够纠正码字中任意小于等于t位误码的错误图样小 $2^{r}$

长度为n,任意小于等于t位错误图样数为

$c_n^0+c_n^1+c_n^2+..+c_n^t$

(n,k) 不同伴随式个数为 $2^r$

则：

$2^r\geq 1+c_n^1+c_n^2+..+c_n^t$

四完备码

若能纠正t个以及以下的全部错误的线性分组码满足

$2^r=1+c_n^1+c_n^2+..c_n^t$

则称这种线性分组码为完备码

汉明码就是一种t=1完备码

$2^r=1+n$

4.1 普洛特金界

确定了(n,k)线性分组码能力上限

下限是 $d_{min}\geq 2t+1$

上限

$d_{min}\leq n\frac{2^{k-1}}{2^{k}-1}$

五例题

5.1 判断线性分组码（n=7,k=1)有无纠正t=2位误码的可能性

下限

$d_{min}\geq 2t+1,d_{min}\geq 5$

上限（普洛特金界）

$d_{min}\leq 7\frac{2^{0}}{2^1-1}$ $,d_{min}\leq \frac{7}{1}$

有可能

5.3 判断线性分组码（n=7,k=2)有无纠正t=2位误码的可能性

下限 $d_{min}\geq 2t+1,d_{min}\geq 5$

上限 $d_{min}\leq 7\frac{2^{2-1}}{2^2-1}$ $\leq \frac{14}{3}$

矛盾，没有可能

5.2 判断线性分组码（n=7,k=3)有无纠正t=2位误码的可能性

下限 $d_{min}\geq 2t+1,d_{min}\geq 5$

上限 $d_{min}\leq 7\frac{2^{3-1}}{2^3-1}$ $,d_{min}\leq 4$

矛盾，没有可能