相關(guān)知識(shí)點(diǎn)

在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn) CRC 的檢錯(cuò)技術(shù)。

循環(huán)冗余檢驗(yàn)的原理

在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組 k 個(gè)比特。 在每組 M 后面再添加供差錯(cuò)檢測(cè)用的 n 位冗余碼，然后一起發(fā)送出去。

冗余碼的計(jì)算

用二進(jìn)制的模 2 運(yùn)算進(jìn)行 2n 乘 M 的運(yùn)算，這相當(dāng)于在 M 后面添加 n 個(gè) 0。 得到的 (k + n) 位的數(shù)除以事先選定好的長(zhǎng)度為 (n + 1) 位的除數(shù) P，得出商是 Q 而余數(shù)是 R，余數(shù) R 比除數(shù) P 少 1 位，即 R 是 n 位。 將余數(shù) R 作為冗余碼拼接在數(shù)據(jù) M 后面，一起發(fā)送出去。

接收端對(duì)收到的每一幀進(jìn)行 CRC 檢驗(yàn)

(1) 若得出的余數(shù) R = 0，則判定這個(gè)幀沒(méi)有差錯(cuò)，就接受 (accept)。 (2) 若余數(shù) R ≠ 0，則判定這個(gè)幀有差錯(cuò)，就丟棄。 但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。 只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù) P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。

冗余碼的計(jì)算舉例

現(xiàn)在 k = 6, M = 101001。 設(shè) n = 3, 除數(shù) P = 1101， 被除數(shù)是 2nM = 101001000。 模 2 運(yùn)算的結(jié)果是：商 Q = 110101，余數(shù) R = 001。 把余數(shù) R 作為冗余碼添加在數(shù)據(jù) M 的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM + R，即：101001001，共 (k + n) 位。

模2除法步驟

用除數(shù)對(duì)被除數(shù)最高幾位做模2減，沒(méi)有借位； 除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對(duì)余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位； 一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)就是最終余數(shù)。

代碼實(shí)現(xiàn)

package computernetwork;// 循環(huán)冗余檢驗(yàn) Cyclic Redundancy Check (CRC)public class CRC { private int[] generatingCode; // 生成碼 // 設(shè)置生成碼 public void setGeneratingCode(String str) {generatingCode = stringToArray(str); } // 獲取幀檢驗(yàn)序列 public String getFCS(String message) {for (int i = 0; i < generatingCode.length - 1; i++) { message += '0';}return getRemainder(stringToArray(message)); } // 判斷接受碼是否產(chǎn)生跳變 public boolean judge(String res) {return Integer.parseInt(getRemainder(stringToArray(res))) == 0; } // 將01字符串轉(zhuǎn)換為數(shù)組 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; } // 求余數(shù) 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')); // 1110System.out.println(crc.judge('11010110111110')); // trueSystem.out.println(crc.judge('11010110111011')); // false }}總結(jié)

到此這篇關(guān)于Java實(shí)現(xiàn)計(jì)網(wǎng)循環(huán)冗余檢驗(yàn)算法的文章就介紹到這了,更多相關(guān)Java計(jì)網(wǎng)循環(huán)冗余檢驗(yàn)算法內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！