基本比特差錯的檢測演算法

㈠ 數據鏈路層中的鏈路的三個基本問題（幀定界、透明傳輸和差錯檢測）為什麼都必須加以解決

封裝成幀就是在一段數據的前後分別添加首部和尾部，這樣就構成了一個幀。接收端在收到物理層上交的比特流後，就能根據首部和尾部的標記，從比特流中識別幀的開始和結束。

當傳送的幀是用文本文件組成的幀時，其數據部分顯然不會出現像SOH或EOT這樣的幀定界控制字元。可見不管從鍵盤上輸入什麼字元都可以放在這樣的幀中傳輸過去，因此這樣的傳輸就是透明傳輸。

數據鏈路層並不需要給網路層提供「可靠傳輸」的服務，必須讓數據鏈路層向上提供可靠傳輸。因此在CRC的基礎上，增加了幀編號、確認和重傳機制。

(1)基本比特差錯的檢測演算法擴展閱讀：

數據鏈路層的最基本的功能是向該層用戶提供透明的和可靠的數據傳送基本服務。透明性是指該層上傳輸的數據的內容、格式及編碼沒有限制，也沒有必要解釋信息結構的意義；可靠的傳輸使用戶免去對丟失信息、干擾信息及順序不正確等的擔心。

在物理層中這些情況都可能發生，在數據鏈路層中必須用糾錯碼來檢錯與糾錯。數據鏈路層是對物理層傳輸原始比特流的功能的加強，將物理層提供的可能出錯的物理連接改造成為邏輯上無差錯的數據鏈路，使之對網路層表現為一無差錯的線路。

㈡ 數據鏈路層的三個基本問題是什麼

1. 封裝成幀
封裝成幀(framing)：就是在一段數據的前後分別添加首部和尾部，這樣就構成了一個幀。
2. 透明傳輸
由於幀的開始和結束的標記是使用專門指明的控制字元，因此，所傳輸的數據中的任何8比特的組合一定不允許和用作幀定界的控制字元的比特編碼一樣，否則就會出現幀定界的錯誤。
3. 差錯檢測
傳輸差錯：可分為兩大類，一類就是最基本的比特差錯，另一類就是收到的幀並沒有出現比特錯誤，但卻出現了幀丟失、幀重復或幀失序。

㈢ 計算機通信中通常使用的差錯檢驗方法

在LDPC（Low－Density Parity－Check，低密度奇偶校驗）碼用於糾錯碼時，能夠抑制吞吐量下降並且高精度地進行差錯檢測的無線通信裝置。在該無線通信裝置中，CRC（Cyclic Rendancy Check，循環冗餘校驗）編碼單元（101）基於LDPC碼的校驗矩陣的列權重，只對發送比特串的一部分比特進行CRC編碼而生成CRC編碼數據，LDPC編碼單元（102）使用與CRC編碼單元（101）進行CRC編碼時使用的校驗矩陣相同的校驗矩陣，對CRC編碼數據進行LDPC編碼而生成LDPC編碼數據

㈣ 8bit數據怎麼差錯校驗，就是一共8BIT,其中7BIT為有效數據，1BIT為校驗位，有沒有比較好一點的校驗演算法程序

我當時做串口通信時用的是CRC-CCITT循環冗餘校驗演算法。和你的這種演算法有點不一樣，但是差不多，你可以試下，如果要代碼的話，我也有。給你個網路的鏈接，你看下嘛，呵呵。忘說了，我校驗演算法是用的比特型演算法。你稍微對CRC演算法改良下就滿足你的需要了，希望幫到你了，呵呵。http://ke..com/view/1664507.htm

㈤ 常用的差錯控制編碼方法有哪些

常用的差錯控制編碼方法有：奇偶校驗、恆比碼、矩陣碼、循環冗餘校驗碼、卷積碼、Turbo碼。

1、奇偶校驗

奇偶校驗是一種校驗代碼傳輸正確性的方法。根據被傳輸的一組二進制代碼的數位中「1」的個數是奇數或偶數來進行校驗。採用奇數的稱為奇校驗，反之，稱為偶校驗。

採用何種校驗是事先規定好的。通常專門設置一個奇偶校驗位，用它使這組代碼中「1」的個數為奇數或偶數。若用奇校驗，則當接收端收到這組代碼時，校驗「1」的個數是否為奇數，從而確定傳輸代碼的正確性。

2、恆比碼

恆比碼一般指定比碼 。

定比碼是指一組碼中1和0的碼元個數成一定比例的一種編碼。換言之，它是選用比特序列中1和0碼元之比例為定值，所以又稱為恆比碼。定比碼是一種常用的檢錯碼。

3、矩陣碼

矩陣碼屬二維條碼的一種，是將圖文和數據編碼後，轉換成一個二維排列的多格黑白小方塊圖形。

矩陣式二維條形碼是以矩陣的形式組成，在矩陣相應元素位置上，用點(Dot)的出現表示二進制的 「1」，不出現表示二進制的 「0」，點的排列組合確定了矩陣碼所代表的意義。其中點可以是方點、圓點或其它形狀的點。矩陣碼是建立在電腦圖像處理技術、組合編碼原理等基礎上的圖形符號自動辨識的碼制，已較不適合用「條形碼」稱之。

4、循環冗餘校驗碼

循環冗餘校驗碼（CRC），簡稱循環碼，是一種常用的、具有檢錯、糾錯能力的校驗碼，在早期的通信中運用廣泛。循環冗餘校驗碼常用於外存儲器和計算機同步通信的數據校驗。奇偶校驗碼和海明校驗碼都是採用奇偶檢測為手段檢錯和糾錯的(奇偶校驗碼不具有糾錯能力)，而循環冗餘校驗則是通過某種數學運算來建立數據位和校驗位的約定關系的。

5、卷積碼

卷積碼將k個信息比特編成n個比特，但k和n通常很小，特別適合以串列形式進行傳輸，時延小。卷積碼的糾錯性能隨m的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優於分組碼。

6、Turbo碼

Turbo碼是Claude.Berrou等人在1993年首次提出的一種級聯碼。Turbo碼有一重要特點是其解碼較為復雜，比常規的卷積碼要復雜的多，這種復雜不僅在於其解碼要採用迭代的過程，而且採用的演算法本身也比較復雜。這些演算法的關鍵是不但要能夠對每比特進行解碼，而且還要伴隨著解碼給出每比特譯出的可靠性信息，有了這些信息，迭代才能進行下去。

(5)基本比特差錯的檢測演算法擴展閱讀：

差錯控制編碼是指在實際信道上傳輸數字信號時，由於信道傳輸特性不理想及加性雜訊的影響，所收到的數字信號不可避免地會發生錯誤。

為了在已知信噪比的情況下達到一定的誤比特率指標，首先應合理設計基帶信號，選擇調制、解調方式，採用頻域均衡和時域均衡，使誤比特率盡可能降低，但若誤比特率仍不能滿足要求，則必須採用信道編碼，即差錯控制編碼。

差錯控制編碼的基本做法是：在發送端被傳輸的信息序列上附加一些監督碼元，這些多餘的碼元與信息碼元之間以某種確定的規則相互關聯（約束）。接收端按照既定的規則檢驗信息碼元與監督碼元之間的關系，一旦傳輸過程中發生差錯，則信息碼元與監督碼元之間的關系將受到破壞，從而可以發現錯誤，乃至糾正錯誤。研究各種編碼和解碼方法正式差錯控制編碼所要解決的問題。

㈥ 關於計算機網路的crc計算

我們知道，一台主機向另外一台主機發送報文的時候，需要一層層經過自己的協議棧進行數據封裝，到達最後一層（四層協議的網路介面層）時需要在幀尾部添加FCS校驗碼（通過CRC演算法得出）。當對端主機收到時，在接收端同樣通過CRC演算法進行驗證，確認傳輸過程中是否出現錯誤。它只能確認一個幀是否存在比特差錯，但沒有提供解決措施。

循環冗餘校驗的原理

• 在發送端，先把數據劃分為組（即：一幀）。假定每組 k 個比特。

• 在每組後面，添加供差錯檢測用的 n 位冗餘碼一起發送。即：實際發送長度為：k+n 比特。

• 發送前雙方協商n+1位的除數P，方便接收方收到後校驗。

• 給K比特的數據添加除數減一個0（P-1）作為被除數，與第三步確定的除數做「模2除法」。得出的余數即FCS校驗序列，它的位數也必須是（P-1）。

• 將FCS校驗序列添加至K個比特位的後面發送出去。

• 接收方對接收到的每一幀進行校驗，若得出的余數 R = 0，則判定這個幀沒有差錯，就接受(accept)。若余數 R ≠ 0，則判定這個幀有差錯，就丟棄。

對「模2除法」進行說明：

「模2除法」與「算術除法」類似，但它既不向上位借位，也不比較除數和被除數的相同位數值的大小，只要以相同位數進行相除即可。模2加法運算為：1+1=0，0+1=1，0+0=0，無進位，也無借位；模2減法運算為：1-1=0，0-1=1，1-0=1，0-0=0，也無進位，無借位。相當於二進制中的邏輯異或運算。

計算示例


那麼接收方拿到的就是：101001001。再以它為被除數，1101為除數進行「模2除法」。

㈦ 什麼是差錯校驗要具體點的

差錯校驗是在數據通信過程中能發現或糾正差錯，把差錯限制在盡可能小的允許范圍內的技術和方法。

1. 信號在物理信道中傳輸時，線路本身電器特性造成的隨機雜訊、信號幅度的衰減、頻率和相位的畸變、電器信號在線路上產生反射造成的迴音效應、相鄰線路間的串擾以及各種外界因素（如大氣中的閃電、開關的跳火、外界強電流磁場的變化、電源的波動等）都會造成信號的失真。在數據通信中，將會使接受端收到的二進制數位和發送端實際發送的二進制數位不一致，從而造成由「0」變成「1」或由「1」變成「0」的差錯
常用的校驗方法有如下：
奇偶校驗碼

奇偶校驗碼是一種通過增加冗餘位使得碼字中「1」的個數為奇數或偶數的編碼方法，它是一種檢錯碼。

1.垂直奇偶校驗的特點及編碼規則

特點：垂直奇偶校驗又稱縱向奇偶校驗，它能檢測出每列中所有奇數個錯，但檢測不出偶數個的錯。因而對差錯的漏檢率接近1/2。

位\數字 0 1 2 3 4 5 6 7 8 9
C1 0 1 0 1 0 1 0 1 0 1
C2 0 0 1 1 0 0 1 1 0 0
C3 0 0 0 0 1 1 1 1 0 0
C4 0 0 0 0 0 0 0 0 1 1
C5 1 1 1 1 1 1 1 1 1 1
C6 1 1 1 1 1 1 1 1 1 1
C7 0 0 0 0 0 0 0 0 0 0
偶 C0 0 1 1 0 1 0 0 1 1 0
奇 1 0 0 1 0 1 1 0 0 1

2.水平奇偶校驗的特點及編碼規則
特點：水平奇偶校驗又稱橫向奇偶校驗，它不但能檢測出各段同一位上的奇數個錯，而且還能檢測出突發長度<=p的所有突發錯誤。其漏檢率要比垂直奇偶校驗方法低，但實現水平奇偶校驗時，一定要使用數據緩沖器。

位\數字 0 1 2 3 4 5 6 7 8 9 偶校驗
C1 0 1 0 1 0 1 0 1 0 1 1
C2 0 0 1 1 0 0 1 1 0 0 0
C3 0 0 0 0 1 1 1 1 0 0 0
C4 0 0 0 0 0 0 0 0 1 1 0
C5 1 1 1 1 1 1 1 1 1 1 1
C6 1 1 1 1 1 1 1 1 1 1 1
C7 0 0 0 0 0 0 0 0 0 0 0

3.水平垂直奇偶校驗的特點及編碼規則
特點：水平垂直奇偶校驗又稱縱橫奇偶校驗。它能檢測出所有3位或3位以下的錯誤、奇數個錯、大部分偶數個錯以及突發長度<=p+1的突發錯。可使誤碼率降至原誤碼率的百分之一到萬分之一。還可以用來糾正部分差錯。有部分偶數個錯不能測出。適用於中、低速傳輸系統和反饋重傳系統。

位\數字 0 1 2 3 4 5 6 7 8 9 校驗碼字

C1 0 1 0 1 0 1 0 1 0 1 1
C2 0 0 1 1 0 0 1 1 0 0 0
C3 0 0 0 0 1 1 1 1 0 0 0
C4 0 0 0 0 0 0 0 0 1 1 0
C5 1 1 1 1 1 1 1 1 1 1 1
C6 1 1 1 1 1 1 1 1 1 1 1
C7 0 0 0 0 0 0 0 0 0 0 0
C8 0 1 1 0 1 0 0 1 1 0 1

2.5.3 循環冗餘碼（CRC）
1.CRC的工作方法
在發送端產生一個循環冗餘碼，附加在信息位後面一起發送到接收端，接收端收到的信息按發送端形成循環冗餘碼同樣的演算法進行校驗，若有錯，需重發。
2.循環冗餘碼的產生與碼字正確性檢驗例子。
例1.已知：信息碼:110011 信息多項式:K(X)=X5+X4+X+1
生成碼:11001 生成多項式:G(X)=X4+X3+1(r=4)
求：循環冗餘碼和碼字。
解：1)(X5+X4+X+1)*X4的積是 X9+X8+X5+X4 對應的碼是1100110000。
2)積／G(X)(按模二演算法)。
由計算結果知冗餘碼是1001，碼字就是1100111001。

1 0 0 0 0 1←Q(X)
G(x)→1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0←F(X)*Xr
1 1 0 0 1 ，
1 0 0 0 0
1 1 0 0 1
1 0 0 1←R(X)(冗餘碼)

例2.已知：接收碼字:1100111001 多項式:T(X)=X9+X8+X5+X4+X3+1
生成碼 : 11001 生成多項式:G(X)=X4+X3+1(r=4)
求：碼字的正確性。若正確，則指出冗餘碼和信息碼。
解：1)用字碼除以生成碼，余數為0，所以碼字正確。

1 0 0 0 0 1←Q(X)
G(x)→1 1 0 0 1 )1 1 0 0 1 1 1 0 0 1←F(X)*Xr＋R(x)
1 1 0 0 1 ，
1 1 0 0 1
1 1 0 0 1
0←S(X)(余數)

2)因r=4，所以冗餘碼是：11001，信息碼是:110011

3.循環冗餘碼的工作原理
循環冗餘碼CRC在發送端編碼和接收端校驗時，都可以利用事先約定的生成多項式G(X)來得到，K位要發送的信息位可對應於一個(k-1)次多項式K(X),r位冗餘位則對應於一個(r-1)次多項式R(X)，由r位冗餘位組成的n=k+r位碼字則對應於一個(n-1)次多項式T(X)=Xr*K(X)+R(X)。

4.循環冗餘校驗碼的特點
1)可檢測出所有奇數位錯；
2)可檢測出所有雙比特的錯；
3)可檢測出所有小於、等於校驗位長度的突發錯。

2.5.4 海明碼

1.海明碼的概念

海明碼是一種可以糾正一位差錯的編碼。它是利用在信息位為k位，增加r位冗餘位，構成一個n=k+r位的碼字，然後用r個監督關系式產生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯。它必需滿足以下關系式：
2r>=n+1 或 2r>=k+r+1
海明碼的編碼效率為：
R=k/(k+r)
式中 k為信息位位數
r為增加冗餘位位數

2.海明碼的生成與接收

方法一：

1)海明碼的生成。

例1.已知：信息碼為："0010"。海明碼的監督關系式為：
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6

求：海明碼碼字。

解：1)由監督關系式知冗餘碼為a2a1a0。
2)冗餘碼與信息碼合成的海明碼是："0010a2a1a0"。
設S2=S1=S0=0,由監督關系式得：
a2=a4+a5+a6=1
a1=a3+a5+a6=0
a0=a3+a4+a6=1
因此，海明碼碼字為："0010101"

2)海明碼的接收。

例2.已知：海明碼的監督關系式為：
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
接收碼字為："0011101"(n=7)

求：發送端的信息碼。

解：1)由海明碼的監督關系式計算得S2S1S0=011。
2)由監督關系式可構造出下面錯碼位置關系表：

S2S1S0 000 001 010 100 011 101 110 111
錯碼位置 無錯 a0 a1 a2 a3 a4 a5 a6

3)由S2S1S0=011查表得知錯碼位置是a3。
4)糾錯--對碼字的a3位取反得正確碼字："0 0 1 0 1 0 1"
5)把冗餘碼a2a1a0刪除得發送端的信息碼："0010"

方法二：(不用查表，方便編程)－－－推薦！！！

1)海明碼的生成（順序生成法）。

例3.已知：信息碼為：" 1 1 0 0 1 1 0 0 " (k=8)
求：海明碼碼字。
解：1)把冗餘碼A、B、C、…，順序插入信息碼中，得海明碼
碼字:" A B 1 C 1 0 0 D 1 1 0 0 "
碼位: 1 2 3 4 5 6 7 8 9 10 11 12
其中A,B,C,D分別插於2k位(k=0,1,2,3)。碼位分別為1,2,4,8。
2)冗餘碼A,B,C,D的線性碼位是：(相當於監督關系式)
A->1,3,5,7,9,11；
B->2,3,6,7,10,11；
C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
D->8,9,10,11,12。
3)把線性碼位的值的偶校驗作為冗餘碼的值(設冗餘碼初值為0)：
A=∑(0,1,1,0,1,0)=1
B=∑(0,1,0,0,1,0)=0
C=∑(0,1,0,0,0) =1
D=∑(0,1,1,0,0) =0
4)海明碼為:"1 0 1 1 1 0 0 0 1 1 0 0"

2)海明碼的接收。

例4.已知：接收的碼字為："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)
求：發送端的信息碼。
解：1)設錯誤累加器(err)初值=0
2)求出冗餘碼的偶校驗和，並按碼位累加到err中：
A=∑(1,0,1,0,1,0)=1 err=err+20=1
B=∑(0,0,0,0,1,0)=1 err=err+21=3
C=∑(1,1,0,0,0) =0 err=err+0 =3
D=∑(0,1,1,0,0) =0 err=err+0 =3
由err≠0可知接收碼字有錯，
3)碼字的錯誤位置就是錯誤累加器(err)的值3。
4)糾錯--對碼字的第3位值取反得正確碼字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位於2k位的冗餘碼刪除得信息碼："1 1 0 0 1 1 0 0"