糾錯碼演算法

⑴ 信道編碼方法 要能解決檢錯和糾結方法！！ 最好有個案例！

我們假設三個比特組成的信息，000 ，011，101，110分別代表著不同的信息。然後在傳輸的過程中，有一個BIT發生了錯誤，比如接收的時候出現了100。我們會發現，沒有100這個編碼，我們就可以知道100是錯誤的。這就是檢查錯誤。但是，我們沒法知道是000的高位出現錯誤還是110的中位出現錯誤，所以它沒有糾錯功能。
但是，如果我們再增加冗餘比特，比如我們就000和111表示兩個信息，這個時候我們再接收到100，我們就會知道是000的高位出現錯誤。這就有了糾錯功能，當然只能糾錯1位比特的錯誤。如果需要更強的糾錯能力，那麼我們需要增加更多的冗餘信息。
不知道你能明白嗎？

⑵ 糾錯編碼技術有多少種

糾錯編碼是BCH碼、Reed-Solomen碼和卷積碼.
BCH碼和Reed-Solomen碼是兩種具有代表性的線性分組、循環碼,對於二元隨機雜訊有很強的糾錯能力,所以普遍應用於各種實際的差錯控制系統.

糾錯編碼是信道編碼的一種，基本原理是發送端在待傳輸的信息序列後按照一定的規則增加一些用於實現糾錯、檢錯的冗餘監督碼元，構成一個碼字再送到信道傳輸；在接收端則按照同樣的規則監測所接收的碼組是否出現錯誤，若發生的錯誤數不大於糾錯碼的糾錯、檢錯能力，則可發生錯誤並且要求發端重新發送該信息序列或者自動加以糾正。

⑶ 糾錯編碼的分類

1．自動請求重發（ARQ）
採用這種方法時，當接收端檢測到所接收的信息有錯以後，通過反向信道向發送端要求重發原信息，直到接收端認可為止，從而達到糾正誤碼的目的。這種方法的優點是糾錯編解碼設備簡單，但需要具備反向信道，且實時性較差。
2．前向糾錯（FEC）
前向差錯控制編碼的基本做法是在發送端被傳輸的信息序列上附加一些監督碼元，這些多餘的監督碼元與信息碼元之間以某種確定的規則相互關聯(約束)。接收端按照既定的關聯規則檢驗信息碼元與監督碼元之間的關系，一旦傳輸過程中發生差錯，則信息碼元與監督碼元之間的關系將受到破壞，從而可以發現錯誤，乃至糾正錯誤。具體說就是接收端對接收到的碼字施加一定的演算法，從而發現誤碼並予以糾正。這種方式的優點是不需要反向信道，糾錯編解碼的實時性較好。缺點是糾錯編解碼較復雜，且糾錯能力有限。
3．混合糾錯（HEC）
該方式是前兩種方式的結合。接收端對所接收的碼流中少量的誤碼可通過前向糾錯方式進行自動糾正；而對超過前向糾正能力的誤碼，但能檢測出來，則接收端通過反向信道請求發端重發，以此對錯碼加以糾正。
以上三種差錯控制方式可以用圖1來概括。無論採用那種糾錯方法，都要在原信息中插入冗餘碼才能實現糾錯或檢錯。由於前向糾錯方法簡單，不需要反向信道，且能實時實現。因此在實時圖像通信系統中，多採用前向糾錯的方法來進行對圖像信號和系統控制信號的差錯控制。
4．BCH糾錯編碼
實測表明，對圖像信息進行了BCH(511，493)的糾錯處理，通過增加4%的冗餘度信息可以將信道誤碼率由10－6改善到10－9，從而確保了圖像信息的可靠傳輸。
糾錯碼的實現框圖如圖2所示，圖像數據首先被分成一個個的493比特的數據組，組與組之間空18比特，有待於插入校驗位。圖像數據組進入BCH糾錯編碼單元，按照上述的BCH(511，493)的演算法，算出18位校驗位。延時單元主要的目的就是補償BCH編碼所花費的時間，使得經編碼輸出的校驗位和相應的數據剛好對齊，然後將兩者復合起來形成一路經BCH糾錯編碼的圖像信號送至多路復用單元和音頻、數據信號進行多路復用。
圖1差錯控制方式
圖2糾錯編碼框圖
在接收端，解碼器對圖像進行BCH解碼。在解碼電路中，解碼器根據18位校驗信號對相應的493點陣圖像信號進行驗算，如果圖像數據中有一位隨機誤碼，則通過這樣的校驗可以將它們自動糾正。如果有2位，則可以將它檢測出來。
5．比特交織
在實際應用中，還可以將比特交織和前向糾錯相結合，以期進一步提高糾錯能力，如圖3所示。FEC和編碼交織在分組前完成，在接收端通過反交織可以使突發錯誤分散開來，這樣，具有糾隨機錯誤能力的糾錯碼能糾突發錯誤，這在無線或分組視頻通信中特別有效。
圖3FEC和比特交織

⑷ 信道編碼的糾錯碼的各種類型

卷積碼非常適用於糾正隨機錯誤，但是，解碼演算法本身的特性卻是：如果在解碼過程中發生錯誤，解碼器可能會導致突發性錯誤。為此在卷積碼的上部採用RS碼塊，RS碼適用於檢測和校正那些由解碼器產生的突發性錯誤。所以卷積碼和RS碼結合在一起可以起到相互補償的作用。卷積碼分為兩種：
(1)基本卷積碼:
基本卷積碼編碼效率為，η=1/2,編碼效率較低,優點是糾錯能力強。
(2)收縮卷積碼
如果傳輸信道質量較好，為提高編碼效率，可以采樣收縮截短卷積碼。有編碼效率為：η=1/2、2/3、3/4、5/6、7/8這幾種編碼效率的收縮卷積碼。
編碼效率高，一定帶寬內可傳輸的有效比特率增大,但糾錯能力越減弱。 1993年誕生的Turbo碼，單片Turbo碼的編碼/解碼器，運行速率達40Mb/s。該晶元集成了一個32×32交織器，其性能和傳統的RS外碼和卷積內碼的級聯一樣好。所以Turbo碼是一種先進的信道編碼技術，由於其不需要進行兩次編碼，所以其編碼效率比傳統的RS+卷積碼要好。
3.4GSM系統中的信道編碼
GSM系統把20ms語音編碼後的數據作為一幀，共260bit，分成50個最重要比特、132個次重要比特和78個不重要比特。
在GSM系統中，對話音編碼後的數據既進行檢錯編碼又進行糾錯編碼。如圖5所示。

首先對50個最重要比特進行循環冗餘編碼(CRC)，編碼後為53bit；再將該53bit與次重要的132bit一起進行約束長度為K=5，編碼效率為R=1/2的卷積編碼，編碼後為2(53+132+4)=378bit；最後再加上最不重要的78bit，形成信道編碼後的一幀共456bit。
3.5IS-95系統中的信道編碼
（1）正向鏈路上的信道編碼
在IS-95系統中，正向鏈路上是以不同的沃爾什(Walsh)函數來區分不同的物理信道的。在用沃爾什函數進行直接擴頻調制之前，要對話音數據或信令數據進行編碼效率R=1/2、約束長度為K=9的信道編碼。由於CDMA系統是受自身干擾的系統，各業務信道上的發射功率受到嚴格的限制。當系統中使用同一頻率信道的用戶較多時，對每個用戶而言，接收信噪比就降低。所以，CDMA系統的話音編碼被設計為多速率的。當接收信噪比較高時，採用較高速率的話音編碼，以獲得較好的接收話音質量；當接收信噪比較低時，就採用較低的話音編碼速率。較低速率的話音編碼數據經卷積編碼後，可進行字元重復。語音編碼數據速率越低，卷積編碼後字元可重復的次數越多，使得在較差信道上傳輸的信號獲得更多的保護。
（2）反向鏈路上的信道編碼
IS-95系統中，反向鏈路上是用不同的長偽隨機序列來區分不同的物理信道的。在用長偽隨機序列進行直接擴頻調制之前，要對語音數據或信令數據進行編碼效率R=1/3(速率集1)或R=1/2(速率集2)、約束長度為K=9的信道編碼。由於同樣的原因，語音編碼同樣被設計為多速率的。當接收信噪比較低時。可採用較低的話音編碼速率、字元重復的方法，提高在信道上傳輸時的抗干擾性能。 在實際應用中，比特差錯經常成串發生，這是由於持續時間較長的衰落谷點會影響到幾個連續的比特，而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時才最有效（如RS只能糾正8個位元組的錯誤）。為了糾正這些成串發生的比特差錯及一些突發錯誤，可以運用交織技術來分散這些誤差，使長串的比特差錯變成短串差錯，從而可以用前向碼對其糾錯，例如：在DVB-C系統中，RS(204,188)的糾錯能力是8個位元組，交織深度為12，那麼糾可抗長度為8×12=96個位元組的突發錯誤。
實現交織和解交織一般使用卷積方式
交織技術對已編碼的信號按一定規則重新排列，解交織後突發性錯誤在時間上被分散，使其類似於獨立發生的隨機錯誤，從而前向糾錯編碼可以有效的進行糾錯，前向糾錯碼加交積的作用可以理解為擴展了前向糾錯的可抗長度位元組。糾錯能力強的編碼一般要求的交織深度相對較低。糾錯能力弱的則要求更深的交織深度。
一般來說，對數據進行傳輸時，在發端先對數據進行FEC編碼，然後再進行交積處理。在收端次序和發端相反，先做去交積處理完成誤差分散，再FEC解碼實現數據糾錯。另外，從上圖可看出，交積不會增加信道的數據碼元。
根據信道的情況不同，信道編碼方案也有所不同，在DVB-T里由於由於是無線信道且存在多徑干擾和其它的干擾，所以信道很「臟」，為此它的信道編碼是：RS+外交積+卷積碼+內交積。採用了兩次交積處理的級聯編碼，增強其糾錯的能力。RS作為外編碼，其編碼效率是188/204（又稱外碼率），卷積碼作為內編碼，其編碼效率有1/2、2/3、3/4、5/6、7/8五種（又稱內碼率）選擇，信道的總編碼效率是兩種編碼效率的級聯疊加。設信道帶寬8MHZ，符號率為6.8966Ms/S，內碼率選2/3，16QAM調制，其總傳輸率是27.586Mbps,有效傳輸率是27.586*(188/204)*(2/3)=16.948Mbps,如果加上保護間隔的插入所造成的開銷，有效碼率將更低。
在DVB-C里，由於是有線信道，信道比較「干凈」，所以它的信道編碼是：RS+交積。一般DVB-C的信道物理帶寬是8MHZ，在符號率為6.8966Ms/s，調制方式為64QAM的系統，其總傳輸率是41.379Mbps,由於其編碼效率為188/204，所以其有效傳輸率是41.379*188/204=38.134Mbps。
在DVB-S里，由於它是無線信道，所以它的信道編碼是：RS+交積+卷積碼。也是級聯編碼。
下圖是DVB-T、DVB-C、DVB-S各自的信道編碼方式： 進行基帶信號傳輸的缺點是其頻譜會因數據出現連「1」和連「0」而包含大的低頻成分，不適應信道的傳輸特性,也不利於從中提取出時鍾信息。解決辦法之一是採用擾碼技術,使信號受到隨機化處理，變為偽隨機序列，又稱為「數據隨機化」和「能量擴散」處理。擾碼不但能改善位定時的恢復質量，還可以使信號頻譜平滑，使幀同步和自適應同步和自適應時域均衡等系統的性能得到改善。
擾碼雖然「擾亂」了原有數據的本來規律，但因為是人為的「擾亂」，在接收端很容易去加擾，恢復成原數據流。
實現加擾和解碼，需要產生偽隨機二進制序列（PRBS）再與輸入數據逐個比特作運算。PRBS也稱為m序列，這種m序列與TS的數據碼流進行模2加運算後，數據流中的「1」和「0」的連續遊程都很短，且出現的概率基本相同。
利用偽隨機序列進行擾碼也是實現數字信號高保密性傳輸的重要手段之一。一般將信源產生的二進制數字信息和一個周期很長的偽隨即序列模2相加，就可將原信息變成不可理解的另一序列。這種信號在信道中傳輸自然具有高度保密性。在接收端將接收信號再加上（模2和）同樣的偽隨機序列，就恢復為原來發送的信息。
在DVB-C系統中的CA系統原理就源於此，只不過為了加強系統的保密性，其偽隨機序列是不斷變化的（10秒變一次），這個偽隨機序列又叫控制字（CW)。
現在出現一種新的信道編碼方法。LDPC編碼。LDPC編碼是最接近香農定理的一種編碼。

⑸ 前向糾錯編碼包括

前向糾錯也叫前向糾錯碼(Forward Error Correction，簡稱FEC)，是增加數據通訊可信度的方法。在單向通訊信道中，一旦錯誤被發現，其接收器將無權再請求傳輸。FEC 是利用數據進行傳輸冗餘信息的方法，當傳輸中出現錯誤，將允許接收器再建數據。

⑹ QR碼的糾錯編碼的演算法是怎樣，公式怎樣使用

QR碼是二維條碼的一種，1994年由日本Denso-Wave公司發明。QR來自英文「Quick
Response」的縮寫，即快速反應的意思，源自發明者希望QR碼可讓其內容快速被解碼[1]。QR碼最常見於日本，並為目前日本最流行的二維空間條碼。QR碼比普通條碼可儲存更多資料，亦無需像普通條碼般在掃描時需直線對准掃描器。

⑺ 求救，關於糾錯碼字的計算

厲害 我 哪天 這些 東西 都得 請教你了

⑻ 糾錯碼的基本原理和性能參數

糾錯碼能夠檢錯或糾錯，主要是靠碼字之間有較大的差別。這可用碼字之間的漢明距離d(x，y)來衡量。它的定義為碼字x與y之間的對應位取不同值的碼元個數。一種糾錯碼的最小距離d定義為該種碼中任兩個碼字之間的距離的最小值。一種碼要能發現e個錯誤,它的最小距離d應不小於e+1。若要能糾正t個錯誤，則d應不小於2t+1。一個碼字中非零碼元的個數，稱為此碼字的漢明重量。一種碼中非零碼字的重量的最小值，稱為該碼的最小重量。對線性碼來說，一種碼的最小重量與其最小距離在數值上是相等的。
在構造線性碼時，數字上是從n維空間中選一k維子空間，且使此子空間內各非零碼字的重量盡可能大。當構造循環碼時,可進一步將每一碼字看成一多項式,將整個碼看成是多項式環中的理想,這一理想是主理想,故可由生成多項式決定；而多項式完全可由它的根規定。這樣,就容易對碼進行構造和分析。這是BCH碼等循環碼構造的出發點。一般地說，構造一種碼時，均設法將它與某種代數結構相聯系，以便對它進行描述，進而推導它的性質，估計它的性能和給出它的解碼方法。若一種碼的碼長為n，碼字數為M,或信息位為h,以及最小距離為d，則可把此碼記作【n,M,d】碼。若此碼為線性碼，常簡記作(n，k)或(n,k,d)碼。人們還常用R=log2M/n表示碼的信息率或簡稱碼率,單位為比特/碼元。R越大,則每個碼元所攜帶的信息量越大，編碼效率越高。 糾錯碼實現中最復雜的部分是解碼。它是糾錯碼能否應用的關鍵。根據式(1),採用的碼長n越大,則誤碼率越小。但n越大，編譯碼設備也越復雜,且延遲也越大。人們希望找到的解碼方法是:誤碼率隨碼長n的增加按指數規律下降;解碼的復雜程度隨碼長n的增加接近線性地增加；解碼的計算量則與碼長n基本無關。可惜，已經找到的碼能滿足這樣要求的很少。不過由於大規模集成電路的發展，即使應用比較復雜的但性能良好的碼，成本也並不太高。因此，糾錯碼的應用越來越廣泛。
糾錯碼傳輸的都是數字信號。這既可用硬體實現，也可用軟體實現。前者主要用各種數字電路，主要是採用大規模集成電路。軟體實現特別適合計算機通信網等場合。因為這時可以直接利用網中的計算機進行編碼和解碼，不需要另加專用設備。硬體實現的速度較高，比軟體可快幾個數量級。
在傳信率一定的情況下，如果採用糾錯碼提高可靠性，要求信道的傳輸率增加，帶寬加大。因此，糾錯碼主要用於功率受限制而帶寬較大的信道，如衛星、散射等系統中。糾錯碼還用在一些可靠性要求較高，但設備或器件的可靠性較差，而餘量較大的場合，如磁帶、磁碟和半導體存儲器等。
在分組碼的研究中，譜分析的方法受到人們的重視。糾同步錯誤碼、算術碼、不對稱碼、不等錯誤糾正碼等，也得到較多的研究。 分組碼是對信源待發的信息序列進行分組（每組K位）編碼，它的校驗位僅同本組的信息位有關。自20世紀50年代分組碼的理論獲得發展以來，分組碼在數字通信和數據存儲系統中已被廣泛應用。
分組碼的碼長n和碼字個數M是一個碼的主要構造參數。碼長為n的碼中所有碼字的位數均為n；若要用一個碼傳送k比特信息，則碼字的個數M必須滿足。典型的分組碼是由k位信息位和r位監督位組成的，這樣構成的碼一般稱為系統碼。
分組碼中應用最廣的線性分組碼。線性分組碼中的M個碼字之間具有一定線性約束關系，即這些碼字總體構成了n維線性空間的一個k維子空間。稱此k維子空間為（n，k）線性分組碼。線性系統碼的特點是每個碼字的前k位均由這個碼字所對應的信息位組成，並通過對這k位信息位的線性運算得到後面n—k是位監督位。
線性分組碼中應用最廣的是循環碼，循環碼的主要特徵是任何碼字在循環移位後個碼字。循環碼的優點在於其編碼和解碼手續比一般線性碼簡單，因而易於在設備上實現。在循環碼中，碼字可表示為多項式。循環碼的碼字多項式都可表示成為循環碼的生成多項式與這個碼字所代表的信息多項式的乘積，即，因此一個循環碼可以通過給出其生成多項式來規定。常用的循環碼有BCH碼和RS碼。
網格碼有多種描述方法，網格圖是常用方法之一，它能表示出編碼過程。一個碼率為1/2、包含四種狀態的網格碼的網格圖如圖所示。圖1中00，01，10，11表示編碼器所具有的四種狀態，以「·」示出，從每一狀態出發都存在兩條支路，位於上面的一條支路對應於編碼器輸入為「0」的情況，位於下面的一條支路對應於編碼器輸入為「1」的情況，而每一支路上所列出的兩個二進位碼則表示相應的編碼輸出。因而可知，編碼輸出不僅決定於編碼器的當前輸入，還決定於編碼器的狀態，例如在圖中從「00」狀態出發；，若輸入的二進制數據序列為1011，則編碼器的狀態轉移過程為00→01→10→01→11，而相應的編碼輸出序列為11010010。在網格圖中任意兩條從同一狀態出發；，經不同的狀態轉移過程後又歸於另一相同狀態（該狀態也可與初始狀態相同）的路徑間的距離的最小值稱為碼的自由距離。如該圖中的為5。對於卷積碼來說，的計算可簡化為始於且終於零狀態的非全零路徑與全零路徑間距離的最小值。是表徵網格碼糾錯能力的重要參數。維特比演算法是廣泛採用的網格碼的解碼方法。由於網格碼的狀態越多，解碼越復雜，所以狀態個數是度量網格碼解碼復雜性的重要參數。一般說來可以通過增大解碼復雜性來增加，從而提高碼的糾錯能力。
BCH碼、網格碼已被廣泛地應用於移動通信、衛星通信和頻帶數據傳輸中。RS碼也被廣泛應用於光碟的存儲中。
大多數糾錯碼是設計來糾隨機誤碼的，可以通過交織的方法使它適用於對突發誤碼的糾錯。交織是一種使得集中出現的突發誤碼在解碼時進行分散化的措施，從而使其不超出糾錯碼的糾錯能力范圍。 卷積碼不對信息序列進行分組編碼，它的校驗元不僅與當前的信息元有關，而且同以前有限時間段上的信息元有關。卷積碼在編碼方法上尚未找到像分組碼那樣有效的數學工具和系統的理論。但在解碼方面，不論在理論上還是實用上都超過了分組碼，因而在差錯控制和數據壓縮系統中得到廣泛應用。

⑼ 身份證號最後一位數字稱之為校驗碼，校驗碼的計算方式是怎樣的

按照相關規定，身份號是由17個數字和1個數字校驗碼組成的。而最後一位校驗碼，就是檢查身份證是否正確的主要依據。它的計算方法，主要是由前17位乘以不同的系數，最後的總和除以11。在這種情況下，得到的余數，就是校驗碼。

那麼我們在反推的時候，就可以用身份證號乘於系數，當最後得出的余數和末尾校驗碼不同時，就代表這個身份證，是一個假的身份證，不符合我們國家的標准。另外，余數對應的數字不同，並不是說余數就一定是最後一位身份證號碼。

看到整個計算過程，我們會發現，想要得出校驗碼，並非一件易事。不過在計算中，有人可能會提出疑問，最終的除以為什麼是取11，而不是其他數字。

其實這個問題的答案很簡單，結合校驗碼的功能，11是最容易檢測出問題的存在。同時，它可以覆蓋到大多數身份證，方便進行校驗。畢竟一個國家人口眾多，校驗碼要做到盡可能覆蓋所有人。