详解汉明纠错码原理以及FPGA实现

一、汉明纠错码简介

  汉明纠错码（Hamming Code）是一种用于检测和纠正数据传输中错误的编码方法。它由理查德·汉明（Richard Hamming）在 1950 年代提出。汉明码的主要特点是能够在传输过程中检测和纠正单个比特错误，同时能够检测到双比特错误。
  现在的通信系统一般都是指香农在1948年贝尔实验室建立的，其模型如下：

  在此通信系统中：

1. 信源：发送信息的来源，一般由文字、图像、语音组成。信源将信息转换成消息。
2. 发送器：将消息转换成信号传输到信道上。
3. 信道：信号在信道中传递，会被噪声干扰，噪声源根据不同的统计特征分为不同类型的噪声，例如噪声模型为高斯正态分布的白噪声。
4. 接收器：将接受到的信号转换为消息。
5. 信宿：将消息还原成信息：文字、图像等。

  我们在前面UART通信中知道了什么是奇偶校验：就是通过增加一位信号的冗余位来判断当前传输信号中1的个数，接收端在接收到信号时也通过奇偶校验位来判断当前接受到的信号是否受到了干扰。但是奇偶校验也有缺点：

1. 就是只能检测当前信号传输中1位数据的错误，不能检测两位或者多位的错误；
2. 只能检测出错误但是不能纠正错误。

  而汉明码简单理解就是升级版的奇偶校验位，他能够检测并且纠正1位信号的错误，能检测出两位的错误但是不能纠正，所以汉明码也叫汉明纠错码。

二、汉明码编码原理以及步骤

  汉明码通过在数据中插入冗余位来实现错误检测和纠正。 对与一个k位的数据插入r位的冗余位来组成汉明码，插入冗余位的位数需要满足公式：

$$2^r>=k+r+1$$

  汉明在他的第一篇论文中给出的例子是：信息一共4位，增加l3位冗余位一共组7位编码，满足$2^3>=3+4+1$，所以汉明码也叫74码。原理是使用简单的奇偶校验，再通过分组的方式进行编码，原理如下：
  假如一个4位信号data从高到低 = {d3，d2，d1，d0}，需要增加3个冗余位 p2，p1，p0组成7位编码，冗余位的位置由$2^n$来确定，比如第一个冗余位p0的位置为 $2^0=1$，第二个冗余位p1的位置为$2^1=2$，第三个冗余位p2的位置为$2^2=4$等等以此类推。

1. 第一步：确认编码后数据中信息位和冗余位的位置，根据上面冗余位的位置可知，冗余位为1，2，4，8等等，所以编码后的数据为：

2. 第二步：将每个原始数据位的位置拆分成n个冗余位数据位的位置之和

• 由上面表格可知：原始数据位的位置为7，6，5，3；冗余数据位的位置为4，2，1。
• 数据位7 = 4 + 2 + 1，表示编码后的数据第7位由第4位p2，第2位p1和第1位p0冗余数据来校验；
• 数据位6 = 4 + 2，表示编码后的数据第6位由第4位p2和第2位p1冗余数据来校验；
• 数据位5 = 4 + 1，表示编码后的数据第5位由第4位p2和第1位p0冗余数据来校验；
• 数据位3 = 2 + 1，表示编码后的数据第3位由第2位p1和第1位p0冗余数据来校验；

3. 第三步：根据上面的拆解结果进行分组

• 由上可知，第1位冗余位p0需要校验数据第7位，数据第5位，数据第3位；因此把(p0，d3，d1，d0)分成偶校验第一组；
• 第2位冗余位p1需要校验数据第7位，数据第6位，数据第3位，因此把（p1，d3，d2，d0）分成偶校验第二组；
• 第3位冗余位p2需要校验数据第7位，数据第6位，数据第5位，因此把（p2，d3，d2，d1）分成偶校验第三组；
     分组后的结果如下所示：

4. 第四步：根据各分组的偶校验确定p0，p1，p2的值

• 在偶校验第0组中，如果（d3，d1，d0）中1的个数为偶数个，则p0=0，否则p0=1；
• 在偶校验第1组中，如果（d3，d2，d0）中1的个数为偶数个，则p1=0，否则p1=1；
• 在偶校验第2组中，如果（d3，d2，d1）中1的个数为偶数个，则p2=0，否则p2=1；

   举个例子：如果待发送的信息数据为{d3，d2，d1，d0}={1，1，0，1}，填入表格中则为：

• 在偶校验第0组中，（d3，d1，d0）中1的个数为偶数个，所以p0=0；
• 在偶校验第1组中，（d3，d2，d0）中1的个数为奇数个，所以p1=1；
• 在偶校验第2组中，（d3，d2，d1）中1的个数为偶数个，所以p2=0；
• 最终编码后的数据为{1，1，0，0，1，1，0}

三、汉明码纠错原理以及步骤

   由于偶校验分组中都可以发现这一组中奇数个错误，所以在汉明分组中的交集出就能指出错误的位置，如下图所示：

   例如上面的例子中，原始信息为{d3，d2，d1，d0}={1，1，0，1}，经过汉明编码后变成为{1，1，0，0，1，1，0}；如果传输过程中某一位发生了错误，如第4位被打反数据变成{1，1，0，1，1，1，0}，接收方将收到数据后继续分组：

   在偶校验第0组中，（d3，d1，d0）中1的个数为偶数个，接受到的p0=0，正确；
   在偶校验第1组中，（d3，d2，d0）中1的个数为奇数个，接受到的p1=1，正确；
   在偶校验第2组中，（d3，d2，d1）中1的个数为偶数个，接受到的p2=1，错误；

   如上所示，三个分组中只有偶校验第2组发生了错误，其它两组都是正确的，因此三个分组没有交集，错误的只有冗余位p2，原始数据位没有发生错误，因此恢复出来的原始数据就是{1，1，0，1}，和发送的原始数据与一致。

   再用相同的例子：原始信息为{d3，d2，d1，d0}={1，1，0，1}，经过汉明编码后变成为{1，1，0，0，1，1，0}；如果传输过程中第5位发生了错误，接收到的信号为{1，1，1，0，1，1，0}，接收方依然对其分组检验如下所示：

   在偶校验第0组中，（d3，d1，d0）中1的个数为奇数个，接受到的p0=0，错误；
   在偶校验第1组中，（d3，d2，d0）中1的个数为奇数个，接受到的p1=1，正确；
   在偶校验第2组中，（d3，d2，d1）中1的个数为奇数个，接受到的p2=0，错误；

   如上分析所示，错误的是第0组和第2组，第一组正确；所以错误的位置为第0组和第2组的交集处 d1，然后接收方对其位置信号打反处理恢复为正确的信号{1，1，0，1}和原始发送的信息一致，其它位以此类推。

四、FPGA实现74汉明编码器

   我们先来实现一下4位数据编码成7位汉明码的过程；原理我们已经知道了，就是增加3位冗余位来组成新的7位数据；3个冗余位的计算过程我们也知道了，就是统计对应分组里面1的个数；我们直接开始仿真来看看编码器是否正确，仿真代码如下：

`timescale 1ns / 1ps
module tb_hanming_code_top();

    reg                                                 sys_clk ;
    reg                                                 sys_rst ;
    reg             [3:0]                               data_in ;
    reg                                                 data_valid  ;
    wire            [6:0]                               encode_data ;
    wire                                                encode_data_valid   ;
    reg             [6:0]                               hanming_data_in ;
    reg                                                 hanming_data_valid ;
    wire            [3:0]                               decode_data ;
    wire                                                decode_data_valid ;  

initial begin
    sys_clk = 0;
    sys_rst = 1;
    data_in = 0;
    data_valid = 0;
    #201;
    @(posedge sys_clk)  
    sys_rst = 0;
    #1000;
    forever begin
        @(posedge sys_clk)
        data_in <= {$random} % 16;
        data_valid <= 1'b1; 
    end    
    #100000;
    $stop;
end

always #5 sys_clk = ~sys_clk;

hanming_code_top u_hanming_code_top(
    .sys_clk             ( sys_clk             ),
    .sys_rst             ( sys_rst             ),
    .data_in             ( data_in             ),
    .data_valid          ( data_valid          ),
    .encode_data         ( encode_data         ),
    .encode_data_valid   ( encode_data_valid   ),
    .hanming_data_in     ( hanming_data_in     ),
    .hanming_data_valid  ( hanming_data_valid  ),
    .decode_data         ( decode_data         ),
    .decode_data_valid   ( decode_data_valid   )
);

endmodule

   我们直接生成4位的随机数给编码器，然后观察编码后的数据是否正确。

   第一个数据{0，1，0，0}经过编码后变成{0，1，0，1，0，1，0}，我们手动算一下：

• 在偶校验第0组中，（d3，d1，d0）中1的个数为偶数个，所以p0=0；
• 在偶校验第1组中，（d3，d2，d0）中1的个数为奇数个，所以p1=1；
• 在偶校验第2组中，（d3，d2，d1）中1的个数为奇数个，所以p2=1；
• 最终编码后的数据为{0，1，0，1，0，1，0}和我们编码器出来的一致，其他的也是一样的。

五、FPGA实现74汉明解码器

   解码器也是根据分组来寻找错误的交集来打反bit位，我们在仿真代码中，将编码后的数据直接接到解码的输入端口上：

`timescale 1ns / 1ps
module tb_hanming_code_top();

    reg                                                 sys_clk ;
    reg                                                 sys_rst ;
    reg             [3:0]                               data_in ;
    reg                                                 data_valid  ;
    wire            [6:0]                               encode_data ;
    wire                                                encode_data_valid   ;
    wire            [3:0]                               decode_data ;
    wire                                                decode_data_valid ;  

initial begin
    sys_clk = 0;
    sys_rst = 1;
    data_in = 0;
    data_valid = 0;
    #201;
    @(posedge sys_clk)  
    sys_rst = 0;
    #1000;
    forever begin
        @(posedge sys_clk)
        data_in <= {$random} % 16;
        data_valid <= 1'b1; 
    end    
    #100000;
    $stop;
end


always #5 sys_clk = ~sys_clk;

hanming_code_top u_hanming_code_top(
    .sys_clk             ( sys_clk             ),
    .sys_rst             ( sys_rst             ),
    .data_in             ( data_in             ),
    .data_valid          ( data_valid          ),
    .encode_data         ( encode_data         ),
    .encode_data_valid   ( encode_data_valid   ),
    .hanming_data_in     ( encode_data     ),
    .hanming_data_valid  ( encode_data_valid  ),
    .decode_data         ( decode_data         ),
    .decode_data_valid   ( decode_data_valid   )
);

endmodule

  打开仿真我们可以看到数据被正确的解码出来了，和原始的发送数据一致，接下来我们新增一个加噪声的模块，来对编码后的数据进行随机位取反，让后输入到解码模块里，看解码能否正确的解出原始数据，仿真代码如下：

`timescale 1ns / 1ps
module tb_hanming_code_top();

    reg                                                 sys_clk ;
    reg                                                 sys_rst ;
    reg             [3:0]                               data_in ;
    reg                                                 data_valid  ;
    wire            [6:0]                               encode_data ;
    wire                                                encode_data_valid   ;
    reg             [6:0]                               hanming_data_in ;
    reg                                                 hanming_data_valid ;
    wire            [3:0]                               decode_data ;
    wire                                                decode_data_valid ;  

initial begin
    sys_clk = 0;
    sys_rst = 1;
    data_in = 0;
    data_valid = 0;
    #201;
    @(posedge sys_clk)  
    sys_rst = 0;
    #1000;
    forever begin
        @(posedge sys_clk)
        data_in <= {$random} % 16;
        data_valid <= 1'b1; 
    end    
    #100000;
    $stop;
end

always #5 sys_clk = ~sys_clk;

integer i, j;
initial begin
    i <= 0;
    j <= 0;
    hanming_data_in <= 0;
    hanming_data_valid <= 0;
    forever begin
        @(posedge sys_clk) begin
            i <= {$random}%7;     //随机位数
        #1ns
        for (j=0 ; j<7 ; j = j +1) begin
            if((encode_data_valid == 1'b1)&&(i == j))begin
                hanming_data_in[j] <=  ~encode_data[j];
                hanming_data_valid <= 1;
            end
            else if(encode_data_valid == 1'b1)begin
                hanming_data_in[j] <=  encode_data[j];
                hanming_data_valid <= 1;
            end
            else begin
                hanming_data_in <= 0;
                hanming_data_valid <= 0;
            end
        end
    end
    end
end

hanming_code_top u_hanming_code_top(
    .sys_clk             ( sys_clk             ),
    .sys_rst             ( sys_rst             ),
    .data_in             ( data_in             ),
    .data_valid          ( data_valid          ),
    .encode_data         ( encode_data         ),
    .encode_data_valid   ( encode_data_valid   ),
    .hanming_data_in     ( hanming_data_in     ),
    .hanming_data_valid  ( hanming_data_valid  ),
    .decode_data         ( decode_data         ),
    .decode_data_valid   ( decode_data_valid   )
);

endmodule

  可以看到我们传输过程中模拟噪声，随机将一位的信息取反，解码器依然能正确的恢复出原始数据。