计算机组成原理-汉明码相关计算

Bertha 。 2022-06-02 08:59 440阅读 0赞

今天复习计算机组成原理中看到了汉明码的计算，其中有些知识书上没有完全讲到，我这里根据自己的复习梳理下计算的几个方法。

--------------------

## 检测位的小组 ##

首先检测位的小组的划分书上说的有点不好理解，这里一种比较容易的理解方法是：  
C1：小组中的数最后一个数的二进制数为1：1，3，5，7，9，11  
C2：小组中的倒数第二个数的二进制数为1：2，3，6，7，10，11  
C4：小组中的倒数第三个数的二进制数为1：4，5，6，7，12，13  
C8：小组中的倒数第四个数的二进制数为1：8，9，10，11，12，13  
…  
依次类推

在做题的过程中，基本上只需要记住前四组的前六位就可以了

--------------------

根据不同的代码长度n，所需要的检测位的个数为：`2^k>= n+ k + 1`

经常用的就是：

然后检测位的插入位置是1，2，4，8，…，2^k-1

例如插入三个检测位，传递信息为：b1b2b3b4，则它们的位置安排如下：

<table> 
 <thead> 
  <tr> 
   <th align="left">二进制序号</th> 
   <th align="left">1</th> 
   <th align="left">2</th> 
   <th align="left">3</th> 
   <th align="left">4</th> 
   <th align="left">5</th> 
   <th align="left">6</th> 
   <th align="left">7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">名称</td> 
   <td align="left">C1</td> 
   <td align="left">C2</td> 
   <td align="left">b1</td> 
   <td align="left">C4</td> 
   <td align="left">b2</td> 
   <td align="left">b3</td> 
   <td align="left">b4</td> 
  </tr> 
 </tbody> 
</table>

--------------------

## 计算 ##

**求相应的汉明码**

> 例子：0101 求相应的汉明码

<table> 
 <thead> 
  <tr> 
   <th align="left">二进制序号</th> 
   <th align="left">1</th> 
   <th align="left">2</th> 
   <th align="left">3</th> 
   <th align="left">4</th> 
   <th align="left">5</th> 
   <th align="left">6</th> 
   <th align="left">7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">名称</td> 
   <td align="left">C1</td> 
   <td align="left">C2</td> 
   <td align="left">0</td> 
   <td align="left">C4</td> 
   <td align="left">1</td> 
   <td align="left">0</td> 
   <td align="left">1</td> 
  </tr> 
 </tbody> 
</table>

配偶原则：  
 C 1 = 3 + 5 + 7 = 0 C1 = 3+5+7 = 0 C1=3\+5\+7=0  
 C 2 = 3 + 6 + 7 = 1 C2 = 3+6+7 = 1 C2=3\+6\+7=1  
 C 4 = 5 + 6 + 7 = 0 C4 = 5+6+7 = 0 C4=5\+6\+7=0  
配奇原则：  
 C 1 = 3 + 5 + 7 = 1 C1 = \\frac\{\}\{3+5+7\}=1 C1=3\+5\+7=1  
 C 2 = 3 + 6 + 7 = 0 C2 = \\frac\{\}\{3+6+7\}=0 C2=3\+6\+7=0  
 C 4 = 5 + 6 + 7 = 1 C4 = \\frac\{\}\{5+6+7\}=1 C4=5\+6\+7=1

配偶原则：使小组位中的1的个数为偶数  
奇配原则：取配偶原则的相反数

简单的方法就是直接在二进制序号找出小组中的数

C1：1，**3**，**5**，**7**  
C2：2，**3**，**6**，**7**  
C4：4，**5**，**6**，**7**

最后得到0101的汉明码为（配偶原则）：**0100101**  
最后得到0101的汉明码为（配奇原则）：**1001101**

--------------------

**汉明码的纠错**

> 例子：接收到的汉明码为 0011001，求欲传送的代码

<table> 
 <thead> 
  <tr> 
   <th align="left">二进制序号</th> 
   <th align="left">1</th> 
   <th align="left">2</th> 
   <th align="left">3</th> 
   <th align="left">4</th> 
   <th align="left">5</th> 
   <th align="left">6</th> 
   <th align="left">7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">名称</td> 
   <td align="left">0</td> 
   <td align="left">0</td> 
   <td align="left">1</td> 
   <td align="left">1</td> 
   <td align="left">0</td> 
   <td align="left">0</td> 
   <td align="left">1</td> 
  </tr> 
 </tbody> 
</table>

对于任意不同的n位信息，下面的步骤均可以配置汉明码：

配偶原则：  
 P 1 = 1 + 3 + 5 + 7 = 0 P1 = 1 + 3 + 5 + 7 = 0 P1=1\+3\+5\+7=0  
 P 2 = 2 + 3 + 6 + 7 = 0 P2 = 2 + 3 + 6 + 7 = 0 P2=2\+3\+6\+7=0  
 P 4 = 4 + 5 + 6 + 7 = 0 P4 = 4 + 5 + 6 + 7 = 0 P4=4\+5\+6\+7=0

即P1 P2 P4 = 000，表示没有位错误，故欲传送的信息为：1001

配奇原则：

P 1 = 1 + 3 + 5 + 7 = 1 P1 = \\frac\{\}\{1+3+5+7\}=1 P1=1\+3\+5\+7=1  
 P 2 = 2 + 3 + 6 + 7 = 1 P2 = \\frac\{\}\{2+3+6+7\}=1 P2=2\+3\+6\+7=1  
 P 4 = 4 + 5 + 6 + 7 = 1 P4 = \\frac\{\}\{4+5+6+7\}=1 P4=4\+5\+6\+7=1

即P1 P2 P4 = 111，表示第七位错误，可纠正为：0011000 ，故欲传送的信息为：1000