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