目錄
- 相關知識點
- 在資料鏈路層傳送的幀中，廣泛使用了回圈冗余檢驗 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，那么出現檢測不到的差錯的概率就很小很小，
冗余碼的計算舉例
- 現在 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，除數繼續右移一位；
- 一直做到余數的位數小于除數時，該余數就是最終余數，
代碼實作
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
}
}
ヾ(≧∪≦*)ノ〃
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/276173.html
標籤：java
上一篇：深入理解動態代理模式下的編程思想——JDK動態代理原始碼的底層實作
下一篇：Java 面向物件——封裝