Java实现计网循环冗余检验算法

野性酷女 2022-11-19 01:26 116阅读 0赞

## 目录 ##

*  相关知识点
    
     *  在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。
     *  循环冗余检验的原理
     *  冗余码的计算
     *  接收端对收到的每一帧进行 CRC 检验
     *  冗余码的计算举例
     *  模2除法步骤
 *  代码实现

## 相关知识点 ##

#### 在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。 ####

#### 循环冗余检验的原理 ####

*  在发送端，先把数据划分为组。假定每组 k 个比特。
 *  在每组 M 后面再添加供差错检测用的 n 位冗余码，然后一起发送出去。

#### 冗余码的计算 ####

*  用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。
 *  得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少 1 位，即 R 是 n 位。
 *  将余数 R 作为冗余码拼接在数据 M 后面，一起发送出去。

#### 接收端对收到的每一帧进行 CRC 检验 ####

*  (1) 若得出的余数 R = 0，则判定这个帧没有差错，就接受 (accept)。
 *  (2) 若余数 R ≠ 0，则判定这个帧有差错，就丢弃。
 *  但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。
 *  只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center]

#### 冗余码的计算举例 ####

*  现在 k = 6, M = 101001。
 *  设 n = 3, 除数 P = 1101，
 *  被除数是 2nM = 101001000。
 *  模 2 运算的结果是：商 Q = 110101，余数 R = 001。
 *  把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM + R，即：101001001，共 (k + n) 位。

#### 模2除法步骤 ####

*  用除数对被除数最高几位做模2减，没有借位；
 *  除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位；
 *  一直做到余数的位数小于除数时，该余数就是最终余数。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center 1]

## 代码实现 ##

package computernetwork;
    
    // 循环冗余检验 Cyclic Redundancy Check (CRC)
    public class CRC { 
    
        private int[] generatingCode; // 生成码
    
        // 设置生成码
        public void setGeneratingCode(String str) { 
            generatingCode = stringToArray(str);
        }
    
        // 获取帧检验序列
        public String getFCS(String message) { 
            for (int i = 0; i < generatingCode.length - 1; i++) { 
                message += "0";
            }
            return getRemainder(stringToArray(message));
        }
    
        // 判断接受码是否产生跳变
        public boolean judge(String res) { 
            return Integer.parseInt(getRemainder(stringToArray(res))) == 0;
        }
    
        // 将01字符串转换为数组
        private int[] stringToArray(String str) { 
            char[] chars = str.toCharArray();
            int[] res = new int[chars.length];
            for (int i = 0; i < chars.length; i++) { 
                res[i] = chars[i] - '0';
            }
            return res;
        }
    
        // 求余数
        private String getRemainder(int[] code) { 
            int len = code.length - generatingCode.length + 1;
            for (int i = 0; i < len; i++) { 
                if (code[i] != 0) { 
                    for (int j = 0; j < generatingCode.length; j++) { 
                        code[i + j] ^= generatingCode[j];
                    }
                }
            }
            StringBuilder res = new StringBuilder();
            for (int i = len; i < code.length; i++) { 
                res.append(code[i]);
            }
            return res.toString();
        }
    }
    
    class TestCRC { 
        public static void main(String[] args) { 
            CRC crc = new CRC();
            crc.setGeneratingCode("10011");
            System.out.println(crc.getFCS("1101011011")); // 1110
            System.out.println(crc.judge("11010110111110")); // true
            System.out.println(crc.judge("11010110111011")); // false
        }
    }

ヾ(≧∪≦\*)ノ〃

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/e36866f09a6743ebb1156287f02b0201.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/0bb8cb26084a422f95033f5eff0721fe.png