光學計算機對稱三值數據海明校驗研究

武曲，呂博

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

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

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

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

1 二值數據的海明校驗規則

1.1 二值數據單位誤碼檢測

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

lD-1為信息碼碼長，lP為監督碼碼長：

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

因此：

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

二值邏輯的異或運算相當于不考慮進位時的算術加/減運算。令add表示無進位加運算，∑表示連續的add運算，則式（3）可表示為如式（5）的形式。

校驗傳輸后數據的實質是比對監督碼P各碼位傳輸前后的值是否相等。通常也將該環節計算規定為異或運算，其計算本質是對二者進行無借位減法運算。以sub表示無借位減法運算，Cx表示監督碼的Px碼位傳輸前后的差異，并將其定義為相對校驗位，其與 vpx和的函數關系如式（6）。

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

圖1為文獻［17］建立的適用于校驗二值數據的二叉樹結構的海明樹，其葉結點為由信息碼D各位和監督碼P各位編碼組成的海明碼H，如式（7），當logh+12為整數時，H0,h為監督碼位，否則H0,h為信息碼位。

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

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

當i＞0時，令Vi運算的操作數是2個同級計算Vii的運算結果，即Vi可以成Vii的函數：Vi=V1( )

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

計算某監督碼位Px值的若干信息碼位Dy歸屬同一校驗集合Vi,j，其各分支標識的權值（0或1）對應各相對校驗位Cx可能的取值。

傳輸后，根據式（6）計算得到各相對校驗位的值，基于圖1，選擇與lH相匹配的結點作為錯誤定位出發的根結點，以Cx值為向導尋訪到葉結點，定位出錯碼位，由該根結點到該葉結點所經歷的相對校驗位Cx組成了錯誤定位路徑，記為RC。

1.2 二值數據單位誤碼糾錯

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

2 對稱三值數據的海明校驗規則

2.1 對稱三值邏輯運算

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

表1 對稱三值與運算

圖1 用于二值數據一位檢測一位糾錯的海明樹

表2 對稱三值或運算

表3 對稱三值非運算

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

2.2 對稱三值與二值邏輯

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

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

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

2.3 糾錯表達式通用性證明

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

證明：

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

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

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

圖2 對稱三值數據一位檢測一位糾錯的擴展分支海明樹

對任一Dy必有：

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

對任一Px必有：

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

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

表4 對稱三值無進位加運算

3 計算實例

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

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

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

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

4 結論

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

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

［2］王先超，姚云飛，孫道德，等.三值光學計算機中運算請求調度［J］.計算機工程與應用，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］金翊，何華燦，呂養天.三值光計算機的基本原理［J］.中國科學（E輯），2003，33（2）：111-115.

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

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

［7］王巖，楊奇峰，賈琪，等.空間光通信系統可靠性設計與實現［J］.微電子學與計算機，2010，27（9）：12-15.

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

［9］金翊，顧瑩瑩，左開中.三值光學計算機解碼器的理論，技術和實現［J］.中國科學（信息科學），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］閻華，范宇.差錯控制編碼技術應用研究［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］唐朝京，雷菁.信息論與編碼基礎［M］.北京：電子工業出版社，2010.

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

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

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

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