[科普中國(guó)]-冗余碼

主要內(nèi)容

冗余碼是一種利用了糾錯(cuò)碼的編碼原理，在加密的文件中加入了大量的冗余信息，得到的一種所用符號(hào)數(shù)或信號(hào)碼元數(shù)比表示信息所必需的數(shù)目多的代碼。目前，大多數(shù)研究人員研究的冗余加密技術(shù)是公鑰密碼系統(tǒng)的。

冗余碼加密不論是在糾錯(cuò)編碼研究領(lǐng)域還是在加密領(lǐng)域都是一個(gè)新的值得研究的課題，使得糾錯(cuò)碼和密碼學(xué)相結(jié)合的研究緊密的結(jié)合。在對(duì)明文進(jìn)行冗余加密方面的研究，目前還有許多值的探索的東西，同時(shí)也可以促進(jìn)加密方法實(shí)現(xiàn)多元化，不僅僅限于目前廣為應(yīng)用的幾種加密方法。

分類循環(huán)校驗(yàn)碼循環(huán)校驗(yàn)碼（CRC碼），是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。2

在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域，為了保證數(shù)據(jù)的正確，就不得不采用檢錯(cuò)的手段。在諸多檢錯(cuò)手段中，CRC是最著名的一種，其特點(diǎn)是:檢錯(cuò)能力極強(qiáng)，開(kāi)銷小，易于用編碼器及檢測(cè)電路實(shí)現(xiàn)。從其檢錯(cuò)能力來(lái)看，它所不能發(fā)現(xiàn)的錯(cuò)誤的幾率僅為0.0047%以下。從性能上和開(kāi)銷上考慮，均遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)及算術(shù)和校驗(yàn)等方式。因而，在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域，CRC無(wú)處不在：著名的通訊協(xié)議X.25的FCS(幀檢錯(cuò)序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤(pán)驅(qū)動(dòng)器的讀寫(xiě)采用了CRC16，通用的圖像存儲(chǔ)格式GIF、TIFF等也都用CRC作為檢錯(cuò)手段。CRC的本質(zhì)是模-2除法的余數(shù)，采用的除數(shù)不同，CRC的類型也就不一樣。通常，CRC的除數(shù)用生成多項(xiàng)式來(lái)表示。3

根據(jù)應(yīng)用環(huán)境與習(xí)慣的不同，CRC又可分為以下幾種標(biāo)準(zhǔn)：

1）CRC-12碼；

2）CRC-16碼；

3）CRC-CCITT碼；

4）CRC-32碼。

CRC-12碼通常用來(lái)傳送6-bit字符串。

CRC-16及CRC-CCITT碼則是用來(lái)傳送8-bit字符串，其中CRC-16為美國(guó)采用，而CRC-CCITT為歐洲國(guó)家所采用。CRC-32碼大都被采用在一種稱為Point-to-Point的同步傳輸中。

海明碼海明碼是由1950年由漢明首先提出的，由于海明碼可以糾一位錯(cuò)的線性分組碼，而且它的編碼結(jié)構(gòu)和原理較為簡(jiǎn)單，因此在數(shù)據(jù)傳輸和計(jì)算機(jī)存儲(chǔ)系統(tǒng)中廣泛應(yīng)用。但是同時(shí)，海明碼的最小碼距為3，可以糾正一位錯(cuò)誤，但對(duì)于兩位錯(cuò)不能檢測(cè)，因此即使發(fā)生一位錯(cuò)誤的幾率比較高，但在有較高要求的應(yīng)用中，海明碼一般不被使用。

海明碼是一種可以糾正一位差錯(cuò)的編碼。它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。它必需滿足以下關(guān)系式：2>=n+1 或 2 >=k+r+1

海明碼的編碼效率為：R=k/(k+r)，式中k為信息位位數(shù)，r為增加冗余位位數(shù)。4

海明碼的校驗(yàn)矩陣中冗余信息較多，同時(shí)在7位的海明碼中只存在著4位的信息位，只占其中的4/7，而且7位的海明碼只能糾正4位信息位中的一位錯(cuò)誤。所以，這里我們?cè)囼?yàn)漢明碼對(duì)連續(xù)多位差錯(cuò)糾正的實(shí)現(xiàn)。如果不想再加大碼的距離，同時(shí)又可以糾正連續(xù)多位差錯(cuò)，提高破解密文的復(fù)雜性，可根據(jù)校驗(yàn)矩陣得出的漢明碼重新進(jìn)行組織排列。以16比特的漢明碼為例作說(shuō)明，首先把11個(gè)字節(jié)的數(shù)據(jù)信息比特的16個(gè)字節(jié)漢明碼后再按高低字節(jié)分成兩組。我們將把每列的8個(gè)數(shù)據(jù)編碼每字節(jié)8個(gè)漢明碼的第1位分別取出，組成第1個(gè)字節(jié)。然后，再把這8個(gè)字節(jié)漢明碼的第2位取出，組成第2個(gè)字節(jié)。依此類推，將這組8個(gè)字節(jié)漢明碼處理完畢，得到新的8個(gè)字節(jié)編碼，兩組一共16字節(jié)。我們可以看到這們排序后，每個(gè)字節(jié)包括原來(lái)8個(gè)漢明碼的其中1位。這樣，如果我們對(duì)其中的一組編碼進(jìn)行人為的糾錯(cuò)，使某一編碼字節(jié)連續(xù)8位都發(fā)生改變，實(shí)際是分別使原來(lái)8個(gè)漢明碼的其中1位發(fā)生了改變。只要在糾錯(cuò)前把受干擾的編碼恢復(fù)為原來(lái)正常的排列順序，就可通過(guò)計(jì)算校驗(yàn)碼完成差錯(cuò)的定位及糾錯(cuò)。

BCH碼BCH碼是1959年由Hocquenghon,1960年由Bose和Ray-Chaud-hui分別獨(dú)立得到的糾多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼。BCH碼是迄今為止發(fā)現(xiàn)的一類性能優(yōu)良的線性糾錯(cuò)碼，它的糾錯(cuò)能力強(qiáng)，并且構(gòu)造方便，編譯碼簡(jiǎn)單，有快速的譯碼方法。特別是它具有嚴(yán)格的代數(shù)結(jié)構(gòu)，因此它在編碼理論與實(shí)際中起著重要的作用，也是迄今為止研究的最為詳盡，分析的最為透徹，取得的成果最為豐富的碼類，并且可以用它構(gòu)造某些密碼體制和認(rèn)證碼。

BCH碼是循環(huán)碼種的一種，是糾正多個(gè)隨機(jī)錯(cuò)誤的線性分組碼，是建立在有限域基礎(chǔ)之上的，有著嚴(yán)格的代數(shù)結(jié)構(gòu)。不僅在理論上有重要意義，而且再實(shí)踐中，也是被廣泛應(yīng)用的。1

容錯(cuò)計(jì)算中的應(yīng)用計(jì)算機(jī)采用二進(jìn)制數(shù)。在計(jì)算機(jī)內(nèi)部,表現(xiàn)為元器件的高低電位信號(hào),分別用1和0表示。數(shù)據(jù)沿著數(shù)據(jù)通路,從源部件傳送到目的部件時(shí),若源部件發(fā)送了某一信息(例如低電平0),而目的部件接收的信息與之不同(高電平1),則出現(xiàn)了錯(cuò)誤。在此情況下,計(jì)算機(jī)繼續(xù)工作只會(huì)得出錯(cuò)誤的結(jié)果。導(dǎo)致信息出錯(cuò)的原因很多,主要有元器件的質(zhì)量問(wèn)題、電路故障和噪聲干擾等引起的錯(cuò)誤。人們盡可能?chē)?yán)格測(cè)試、篩選裝機(jī)的元器件,提高系統(tǒng)裝配工藝與質(zhì)量,改善系統(tǒng)的抗干擾能力;但所有這一切都不可能完全避免故障,都難以使系統(tǒng)的平均故障間隔時(shí)間達(dá)到滿意的水平。因此,信息編碼的容錯(cuò)技術(shù)是至關(guān)重要的。5

信息編碼的容錯(cuò)計(jì)算技術(shù)的基本思想是信息冗余(Message Redundancy),即在信息編碼上附加一段冗余編碼,使信息具有發(fā)現(xiàn)本身錯(cuò)誤的能力,甚至能指出錯(cuò)誤的所在位置,然后借助邏輯線路自動(dòng)糾正。利用冗余碼實(shí)現(xiàn)對(duì)數(shù)據(jù)信息的校驗(yàn),目的就是提高計(jì)算機(jī)的可靠性,盡可能提高系統(tǒng)的平均故障間隔時(shí)間。

展望現(xiàn)有的冗余碼加密只適用于密文中冗余信息所占比例較少的情況，不適合對(duì)文字較多的報(bào)價(jià)單進(jìn)行加密，這一點(diǎn)還需要進(jìn)一步改進(jìn)。

正常破解時(shí)，每塊密文信息塊都要找到其中的冗余信息，都需要進(jìn)行糾錯(cuò)，接受方必須知道每塊信息塊中冗余信息的位置，而且這些位置可能是不同的，計(jì)算量加大，因此耗費(fèi)的破解時(shí)間較多。因此，可以設(shè)計(jì)一個(gè)計(jì)算每塊信息中冗與位信息的程序，改進(jìn)該算法，也是未來(lái)發(fā)展的方向。