光學(xué)計算機(jī)對稱三值數(shù)據(jù)海明校驗(yàn)研究

武曲，呂博

（1.上海大學(xué) 材料科學(xué)與工程學(xué)院，上海 200444；2.白城兵器試驗(yàn)中心，白城 137001）

光學(xué)計算機(jī)的研究，尤其是“光互聯(lián)-電運(yùn)算”計算機(jī)已成為研究熱點(diǎn)［1，2］。目前，光網(wǎng)的數(shù)據(jù)交換仍采用“光-電-光”方式，在傳輸過程中，存在傳輸損耗和數(shù)據(jù)出錯的問題。而且，光學(xué)計算機(jī)中存儲和運(yùn)算的數(shù)據(jù)具有三值性［3］，每個數(shù)據(jù)位存在三種可能的物理狀態(tài)，分別由垂直偏振光、水平偏振光和無光強(qiáng)三個光狀態(tài)表示［4］，數(shù)據(jù)位眾多［5］。這些特點(diǎn)均為數(shù)據(jù)可靠性傳輸帶來了挑戰(zhàn)。因此提高數(shù)據(jù)傳輸系統(tǒng)的性能和可靠性十分必要，確保光學(xué)信息在傳輸、存儲、運(yùn)算過程中的可靠性與正確性極為重要［6］。對此，王巖等［7］提出了光通信系統(tǒng)可靠性設(shè)計的硬件和軟件方法。雷鐳［8］和金翊等人［9］研究了在TOC（Ternary Optical Compute）系統(tǒng)監(jiān)控中液晶壞位替換策略和亮暗閾值自動測定技術(shù)。這些探索性成果豐富了光學(xué)計算機(jī)數(shù)據(jù)可靠性傳輸研究。

在數(shù)據(jù)表示上多以對稱三值形式表示光學(xué)計算機(jī)的基本數(shù)據(jù)。三值信息的可靠性存儲、傳輸技術(shù)是光學(xué)計算機(jī)研究的熱點(diǎn)問題。海明碼由美國數(shù)學(xué)家Richard Wesley Hamming（1915年2月11日–1998年1月7日）于1950年正式提出，通過在傳輸?shù)南⒘髦胁迦腧?yàn)證碼的方法，偵測并更正單一bit錯誤［10］。海明規(guī)則在二值數(shù)據(jù)校驗(yàn)及糾錯中已有廣泛應(yīng)用［11-13］，在三值信息檢驗(yàn)及糾錯中應(yīng)用也有嘗試性的探討。金翊等［4］借鑒二值海明碼編碼方法和分組規(guī)則，提出了一種三值海明碼檢錯糾錯原理與方法，對基于海明編碼的可靠性傳輸方法在三值光學(xué)計算機(jī)中的應(yīng)用進(jìn)行了探討，但文中對所述糾錯方法并未給出解析方式表達(dá)，依賴規(guī)則表的糾錯方式對糾錯效率有所制約。

為更有效利用時間資源，本文基于海明樹型結(jié)構(gòu)討論三值光學(xué)計算機(jī)的數(shù)據(jù)可靠性傳輸問題，通過分析二值數(shù)據(jù)海明糾錯過程，建立三值數(shù)據(jù)與二值數(shù)據(jù)校驗(yàn)的聯(lián)系，從解析計算角度分析了一位檢測一位糾錯對稱三值數(shù)據(jù)的海明編碼及校驗(yàn)規(guī)則，定義糾錯因子，推導(dǎo)并證明對稱三值數(shù)據(jù)一位糾錯的解析表達(dá)式，與文獻(xiàn)［3］中的方法相比，節(jié)省了按規(guī)則表糾錯的查表時間；基于海明碼樹結(jié)構(gòu)和糾錯表達(dá)式，使糾錯操作更容易由硬件運(yùn)算器實(shí)現(xiàn)。通過實(shí)例驗(yàn)證了該糾錯表達(dá)式的合理性。

1 二值數(shù)據(jù)的海明校驗(yàn)規(guī)則

1.1 二值數(shù)據(jù)單位誤碼檢測

待傳信息碼Dori有l(wèi)D-1位，為了對Dori在傳輸后進(jìn)行正確性驗(yàn)證，設(shè)置lP位監(jiān)督碼（即校驗(yàn)碼）P，使Dori的各個位Dd和P的各個位Phier按一定規(guī)律交叉排列。將Dori與P組成的數(shù)位串稱為lH-1位的海明編碼，記為Hamming( )lH-1,lD-1，其中，為海明碼碼長，

lD-1為信息碼碼長，lP為監(jiān)督碼碼長：

傳輸后，Hamming( )lH-1,lD-1的lH-1位中出錯位在1位以下（包含1位）的情況有l(wèi)H種可能［14］。有一種可能是傳輸后的Hamming( )lH-1,lD-1是正確的，有l(wèi)H-1種可能是Hamming( )lH-1,lD-1中的某一碼位出錯，錯誤可能出現(xiàn)在信息碼Dori中，也可能出現(xiàn)在監(jiān)督碼P中。lP位的監(jiān)督碼P可以表示 2lP種出錯位在1位以下（包含1位）的情況［15，16］，

因此：

現(xiàn)有研究中，通常將該函數(shù)關(guān)系規(guī)定為異或運(yùn)算。異或運(yùn)算是基本邏輯運(yùn)算“與運(yùn)算”and(A ,B )、“或運(yùn)算”or(A ,B )、“非運(yùn)算”not(A)的組合，如式（4）。

二值邏輯的異或運(yùn)算相當(dāng)于不考慮進(jìn)位時的算術(shù)加/減運(yùn)算。令add表示無進(jìn)位加運(yùn)算，∑表示連續(xù)的add運(yùn)算，則式（3）可表示為如式（5）的形式。

校驗(yàn)傳輸后數(shù)據(jù)的實(shí)質(zhì)是比對監(jiān)督碼P各碼位傳輸前后的值是否相等。通常也將該環(huán)節(jié)計算規(guī)定為異或運(yùn)算，其計算本質(zhì)是對二者進(jìn)行無借位減法運(yùn)算。以sub表示無借位減法運(yùn)算，Cx表示監(jiān)督碼的Px碼位傳輸前后的差異，并將其定義為相對校驗(yàn)位，其與 vpx和的函數(shù)關(guān)系如式（6）。

3.扎實(shí)推進(jìn)留守兒童德育教育工作，使其接觸到的文化生活日漸豐富。學(xué)校應(yīng)該根據(jù)留守兒童的實(shí)際情況，開展多種多樣的活動，讓其可以真正參與進(jìn)來；制訂留守兒童讀書計劃；設(shè)立親情電話；為留守兒童宿舍安裝閉路電視；按時向留守兒童開放微機(jī)室，代理家長及時指導(dǎo)孩子上網(wǎng)學(xué)習(xí)。

圖1為文獻(xiàn)［17］建立的適用于校驗(yàn)二值數(shù)據(jù)的二叉樹結(jié)構(gòu)的海明樹，其葉結(jié)點(diǎn)為由信息碼D各位和監(jiān)督碼P各位編碼組成的海明碼H，如式（7），當(dāng)logh+12為整數(shù)時，H0,h為監(jiān)督碼位，否則H0,h為信息碼位。

將H劃分為NiVstep個交集為空的校驗(yàn)集合Vi,j，每個集合包含i+1個元素。圖中Vi為校驗(yàn)運(yùn)算，表示從校驗(yàn)集合Vi,j中判斷是否有1位出錯位，記為Vi:Vi,j|1，i≥0。Vi,j包含 i+1個 H0,h，j∈[ )

0,NiVstep，經(jīng)過NiVstep步Vi計算后，可定位H中出錯的碼位，其中：

當(dāng)i＞0時，令Vi運(yùn)算的操作數(shù)是2個同級計算Vii的運(yùn)算結(jié)果，即Vi可以成Vii的函數(shù)：Vi=V1( )

Vii，其中i＞ii≥0。一般地，當(dāng) i可以表示為如式（9）所示的hier函數(shù)時，在結(jié)束校驗(yàn)H的全部碼位之前，有式（10）成立。特別地，海明樹的深度與海明碼數(shù)據(jù)位數(shù)滿足式（11）的關(guān)系。

計算某監(jiān)督碼位Px值的若干信息碼位Dy歸屬同一校驗(yàn)集合Vi,j，其各分支標(biāo)識的權(quán)值（0或1）對應(yīng)各相對校驗(yàn)位Cx可能的取值。

傳輸后，根據(jù)式（6）計算得到各相對校驗(yàn)位的值，基于圖1，選擇與lH相匹配的結(jié)點(diǎn)作為錯誤定位出發(fā)的根結(jié)點(diǎn)，以Cx值為向?qū)ぴL到葉結(jié)點(diǎn)，定位出錯碼位，由該根結(jié)點(diǎn)到該葉結(jié)點(diǎn)所經(jīng)歷的相對校驗(yàn)位Cx組成了錯誤定位路徑，記為RC。

1.2 二值數(shù)據(jù)單位誤碼糾錯

由于某一位出錯時其錯誤定位路徑RC中必有相對校驗(yàn)位不為0，且不為0的相對校驗(yàn)位總是只等于1，因此，RC中最接近葉結(jié)點(diǎn)層的非零相對校驗(yàn)位的值Clast即是糾錯因子Ccorrect的值。

2 對稱三值數(shù)據(jù)的海明校驗(yàn)規(guī)則

2.1 對稱三值邏輯運(yùn)算

對稱三進(jìn)制（symmetric ternary）以 1ˉ，0，1表示數(shù)據(jù)［18］。其中表示以0為中心的與1對稱的-1。其邏輯與運(yùn)算and(A ,B )、邏輯或運(yùn)算or(A ,B)、邏輯非運(yùn)算not(A) 規(guī)則如表1、表2、表3［19，20］所示。

表1 對稱三值與運(yùn)算

圖1 用于二值數(shù)據(jù)一位檢測一位糾錯的海明樹

表2 對稱三值或運(yùn)算

表3 對稱三值非運(yùn)算

由表1、表2可以看出，只要操作數(shù)中出現(xiàn)過0，按式（4）進(jìn)行異或運(yùn)算，其結(jié)果恒為0，因此，需要從算術(shù)運(yùn)算角度研究對稱三值信息的海明校驗(yàn)規(guī)則。

2.2 對稱三值與二值邏輯

若傳輸前后海明碼中未有碼位出現(xiàn)改變，則所有相對校驗(yàn)位Cx均為0；否則，會出現(xiàn)某個（某些）Cx為1ˉ或1。雖然Cx的值有三種可能，但傳輸信息正確與否的結(jié)論仍然具有二值性：出錯、未出錯。因此，圖1海明碼樹仍適合于三值海明信息校驗(yàn)。

對稱三值數(shù)據(jù)海明校驗(yàn)時出錯的碼位可能有兩種情況，錯誤值可能在中心值0兩側(cè)的任意一側(cè)，可以認(rèn)為是比原值少1或多1。因此，為了在檢測到錯誤碼位時直接獲得糾錯因子，需要在海明碼樹中保留是哪種情況的出錯：1ˉ或1，對圖1的海明碼樹進(jìn)行分支擴(kuò)展，如圖2所示。由此可知，對稱三值數(shù)據(jù)海明校驗(yàn)仍可以采用海明二叉樹結(jié)構(gòu)，只是指明錯誤的分支具備兩個權(quán)值：1ˉ和1。

基于圖2所示的海明樹對對稱三值表示的信息進(jìn)行校驗(yàn)，若海明碼所有碼位均傳輸正確，則RC中每個相對校驗(yàn)位Cx均為0，由其組成的定位路徑為全0，錯誤位被定位在H0,0；否則，RC中將出現(xiàn)一個或多個Cx值為1ˉ或1，錯誤位即可被準(zhǔn)確定位。

2.3 糾錯表達(dá)式通用性證明

定位錯誤碼位的過程是由圖2所示的海明碼樹的根結(jié)點(diǎn)按各Cx的值選擇相應(yīng)路徑訪問至該碼位所在的葉子結(jié)點(diǎn)，且RC中的各非零Cx值總是保持符號一致，即或全為1ˉ，或全為1。

證明：

對于任一監(jiān)督碼位Px，傳輸前值為vpx，傳輸后值為 vp′x，其值由式（13）計算得到，其中 vdy和vd′y分別表示信息碼位傳輸前后的值，且以式（14）為條件。

若傳輸后某一信息碼位Dy出錯，相對校驗(yàn)位Cx的值由式（15）計算得到。

由于假定前提為傳輸后至多有一位出錯，因此

圖2 對稱三值數(shù)據(jù)一位檢測一位糾錯的擴(kuò)展分支海明樹

對任一Dy必有：

若傳輸后信息碼位均正確，有且只有某一監(jiān)督位Px出錯，則Cx的值由式（17）計算得到。

對任一Px必有：

即當(dāng)傳輸后某一數(shù)據(jù)出錯時，無論該位為信息碼位或監(jiān)督碼位，錯誤定位路徑RC中所有非0的Cx值符號均一致。

因此，糾錯因子式Ccorrect在對稱三值數(shù)據(jù)糾錯中仍然有效，糾錯表達(dá)式式（12）仍然成立。對稱三值數(shù)據(jù)無進(jìn)位加法add( )A,B規(guī)則如表4所示。

表4 對稱三值無進(jìn)位加運(yùn)算

3 計算實(shí)例

設(shè)待傳數(shù)據(jù)由對稱三值信息碼表示為Dori=11ˉ0101ˉ1011ˉ0 ，增設(shè)虛擬位 D-1并編碼后生成海明碼Hamming( )16,12，D與P在海明編碼中的位置及取值如表5所示。

表5 海明碼Hamming( )16,12：H0,h

由式（13）可計算各監(jiān)督碼位傳輸前的值vpx。

表6 任一海明位H′0,h的糾錯

4 結(jié)論

本文通過對二值數(shù)據(jù)一位檢測一位糾錯的海明規(guī)則的分析，以及對對稱三值數(shù)據(jù)邏輯運(yùn)算特點(diǎn)的研究，建立了二值邏輯判斷與三值邏輯計算的聯(lián)系；通過對二值數(shù)據(jù)校驗(yàn)海明樹進(jìn)行分支擴(kuò)展，確定對稱三值數(shù)據(jù)校驗(yàn)的海明樹結(jié)構(gòu)；引入糾錯因子，推導(dǎo)并證明了二值、對稱三值數(shù)據(jù)通用的一位檢測一位糾錯表達(dá)式。該糾錯方式與文獻(xiàn)中按規(guī)則表糾錯的方式相比，節(jié)省了查找規(guī)則的時間，以基本加法計算實(shí)現(xiàn)糾錯，使糾錯運(yùn)算更容易由硬件運(yùn)算器實(shí)現(xiàn)。實(shí)例計算表明，分支擴(kuò)展后的海明碼樹與糾錯表達(dá)式具有合理性，適用于對稱三值數(shù)據(jù)的單位檢測單位糾錯，可以在一定程度上保證三值光學(xué)計算機(jī)在這一特定數(shù)據(jù)表示形式下的數(shù)據(jù)可靠性傳輸。

［1］李梅.三值光計算機(jī)研究綜述［J］.電子設(shè)計工程，2014，22（17）：22-25.

［2］王先超，姚云飛，孫道德，等.三值光學(xué)計算機(jī)中運(yùn)算請求調(diào)度［J］.計算機(jī)工程與應(yīng)用，2012，48（25）：42-47，104.

［3］Shen Yunfu，Pan Lei.Principle of a one-step MSD adderfora ternary opticalcomputer［J］.Science China Information Sciences，2014，57（1）：012017.

［4］金翊，何華燦，呂養(yǎng)天.三值光計算機(jī)的基本原理［J］.中國科學(xué)（E輯），2003，33（2）：111-115.

［5］金翊，歐陽山，宋凱.三值光學(xué)處理器的數(shù)據(jù)位管理理論和技術(shù)［J］.中國科學(xué)（信息科學(xué)），2013，43（3）：361-373.

［6］沈云付，潘磊.擴(kuò)展三值糾一檢二碼原理與設(shè)計［J］.電子學(xué)報，2013，41（8）：1615-1621.

［7］王巖，楊奇峰，賈琪，等.空間光通信系統(tǒng)可靠性設(shè)計與實(shí)現(xiàn)［J］.微電子學(xué)與計算機(jī)，2010，27（9）：12-15.

［8］雷鐳，金翊.三值光學(xué)計算機(jī)解碼器亮度閾值自動測定技術(shù)［J］.計算機(jī)工程與設(shè)計，2012，33（1）：233-237.

［9］金翊，顧瑩瑩，左開中.三值光學(xué)計算機(jī)解碼器的理論，技術(shù)和實(shí)現(xiàn)［J］.中國科學(xué)（信息科學(xué)），2013，43（2）：275-286.

［10］Hamming R W.Error detecting and error correcting codes［J］.The Bell System Technical Journal，1950，29（2）：147-160.

［11］Neuberger G，De Lima F，Carro L，et al.A multiplebitupsettolerantSRAM memory［J］.Acm Transactions on Design Automation of Electronic Systems，2003，8（4）：577-590.

［12］Carlos Munuera.Hamming codes for wet paper steganography［J］.Designs Codes and Cryptography，2015，76（1）：101-111.

［13］Md.Shohidul Islam，Cheol-Hong Kim，Jong-Myon Kim.A GPU-based（8，4）hamming decoder for secure transmission of watermarked medical images［J］.Cluster Computing-The Journal of Networks SoftwareToolsand Applications，2015，18（1）：333-341.

［14］閻華，范宇.差錯控制編碼技術(shù)應(yīng)用研究［J］.航空兵器，2005（4）：30-34.

［15］Bernard Sklar.Digital Communications Fundamentals and Applications Second Edition［M］.Pearson Education Limited；Pearson New International Edition，2013.

［16］唐朝京，雷菁.信息論與編碼基礎(chǔ)［M］.北京：電子工業(yè)出版社，2010.

［17］Wu Qu，Lv Bo，Wang Lei，et al.Hamming code specification analysis based on binary tree［EB/OL］.北京：中國科技論文在線［201409-174］.

［18］左開中，金翊，嚴(yán)軍勇.三值光計算機(jī)的數(shù)值表示及其基本算法［J］.計算機(jī)技術(shù)與發(fā)展，2007，17（9）：8-10，14.

［19］姚從軍.三值邏輯的思想和方法［J］.北京理工大學(xué)學(xué)報：社會科學(xué)版，2010，12（1）：127-131.

［20］馬明輝.三值邏輯與意義理論［J］.西南大學(xué)學(xué)報：社會科學(xué)版，2015，41（1）：21-28.