Java實現計網循環冗餘檢驗算法的方法示例

相關知識點

在數據鏈路層傳送的幀中,廣泛使用瞭循環冗餘檢驗 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
    }
}

總結

到此這篇關於Java實現計網循環冗餘檢驗算法的文章就介紹到這瞭,更多相關Java計網循環冗餘檢驗算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀:

    None Found