基于代數(shù)結(jié)構(gòu)的商空間模型研究

陳林書，王加陽，楊正華，李 力

（1.中南大學信息科學與工程學院，湖南長沙410083；2.湖南科技大學計算機科學與工程學院，湖南湘潭411201；3.哈爾濱工業(yè)大學深圳研究生院，廣東深圳518055）

基于代數(shù)結(jié)構(gòu)的商空間模型研究

陳林書1，2，王加陽1，楊正華1，李 力3

（1.中南大學信息科學與工程學院，湖南長沙410083；2.湖南科技大學計算機科學與工程學院，湖南湘潭411201；3.哈爾濱工業(yè)大學深圳研究生院，廣東深圳518055）

現(xiàn)有商空間模型中論域結(jié)構(gòu)一般被指定為拓撲結(jié)構(gòu)，問題的粒度由等價關(guān)系唯一地確定.當論域結(jié)構(gòu)由拓撲結(jié)構(gòu)變成應(yīng)用廣泛的代數(shù)結(jié)構(gòu)時，引入同余關(guān)系的概念，系統(tǒng)地論證了兩個重要結(jié)論在基于代數(shù)結(jié)構(gòu)的商空間模型中依然成立，即全體同余關(guān)系構(gòu)成的完備半序格和保假，保真原理的存在性.而當確定問題粒度的等價關(guān)系不是一個同余關(guān)系時，對偶地定義了上（下）同余與上（下）商，簡捷地證明了它們的存在性并得出了一些重要性質(zhì)，為商空間的合成與分解提供了理論依據(jù).最后以糾錯碼進行傳輸?shù)穆酚蛇x擇算法為實例，分析了基于代數(shù)結(jié)構(gòu)的商空間模型在網(wǎng)絡(luò)安全傳輸過程中的應(yīng)用.從結(jié)構(gòu)上擴展了現(xiàn)有商空間模型，為商空間理論與代數(shù)理論的結(jié)合提供了基礎(chǔ).

粒計算；商空間；同余閉包；商運算；上（下）商

1 引言

粒計算（GrC）的概念最早由T Y Lin提出，它是模糊集、區(qū)間分析、粗糙集、商空間理論等的超集［1～3］，其研究的目標在于建立粒度化問題求解的一般理論和方法［4～6］.商空間理論由張鈸院士和張鈴教授提出，是最主要的粒計算模型之一.它用三元組（X，f，T）描述問題，其中X表示論域，f是論域的屬性函數(shù)，T表示論域的結(jié)構(gòu)，用論域上的等價關(guān)系R刻畫問題的粒度［7，8］.商空間理論與其他粒計算模型的一個顯著區(qū)別就是引入了對空間結(jié)構(gòu)的描述，這也使得它能具有更強大的描述和求解問題的能力［9～11］.張鈴教授等對論域為拓撲結(jié)構(gòu)的商空間模型進行了系統(tǒng)的研究，形成了相應(yīng)的理論體系［12］，獲得了兩個基本結(jié)論，即粒度世界的完備性和粒度轉(zhuǎn)換時的性質(zhì)保留特性［13］.

事實上，結(jié)構(gòu)是對象描述中最復(fù)雜的，常見的結(jié)構(gòu)有拓撲，代數(shù)，邏輯推理等.如果論域結(jié)構(gòu)為代數(shù)結(jié)構(gòu)，那么商空間基本結(jié)論是否依然成立.本文假設(shè)商空間的論域結(jié)構(gòu)為代數(shù)結(jié)構(gòu)，首先利用同余關(guān)系和閉包的概念定義同余閉包并給出其重要性質(zhì).然后討論商運算的定義及其存在性的充要條件和全體同余關(guān)系是否構(gòu)成完備半序格.接下來分析了任意個同余關(guān)系之和是否仍為同余關(guān)系，即具有商運算的不同粒度世界的下確界是否仍然具有商運算.最后，利用等價關(guān)系與劃分一一對應(yīng)的關(guān)系以及之前所得出的一些結(jié)論進一步討論任意商空間是否總是存在上（下）商，并研究了上（下）商的一些重要性質(zhì).

2 商運算和粒度完備性

為了簡便起見把商空間模型中的三元組簡化成二元組（X，。），X還是表示問題論域，。表示論域的代數(shù)結(jié)構(gòu).代數(shù)結(jié)構(gòu)即運算，可能論域有多種不同的運算，這里僅討論一個二元運算的情況.

2.1同余閉包及其性質(zhì)

定義1 設(shè)R為代數(shù)（X，。）上的一個等價關(guān)系.若R在。運算下具有置換性，即當 a R b時，對?c∈X有a。c R b。c且c。a R c。b，則稱R為關(guān)于運算。的同余關(guān)系，簡稱R為同余關(guān)系.

根據(jù)同余關(guān)系的定義和相關(guān)概念就可很容易地得出如下兩個命題.具體證明從略.

命題1 設(shè)R為代數(shù)（X，。）上一個等價關(guān)系.R是同余關(guān)系的充要條件是當［a］=［b］和［c］=［d］時有［a。c］=［b。d］.

命題2 代數(shù)（X，。）上的全等關(guān)系E和恒等關(guān)系I一定是同余關(guān)系.

引理1 代數(shù)（X，。）上任意個同余關(guān)系的交是同余關(guān)系.

證明 設(shè)｛Rα｝α為代數(shù)（X，。）上若干個同余關(guān)系的集合，記R*=∩αRα.先證一方面，對有于是，從而可知另一方面，對有從而即，亦即因此

現(xiàn)在證明R*是同余關(guān)系.設(shè)和由于，則因此若，則有.同理又因Rα是同余關(guān)系，且，于是因此，R*為同余關(guān)系.綜上所述，引理得證.

閉包概念在數(shù)學上被廣泛運用，下面定義的同余閉包是本文為了從關(guān)系的角度更為簡捷地討論商運算存在性以及上（下）商的存在性而特意引入的.

定義2 設(shè)R為代數(shù)（X，。）上的一個等價關(guān)系，若存在同余關(guān)系c（R）?R，且對任意同余關(guān)系R′?R都有c（R）?R′，則稱c（R）為R的同余閉包.

一言以蔽之，等價關(guān)系R的同余閉包就是包含R的最小同余關(guān)系.

下面給出同余閉包的一些重要性質(zhì).

定理1 代數(shù)（X，。）上任意非空等價關(guān)系都存在同余閉包.

證明 設(shè)R是（X，。）上任意非空等價關(guān)系，令｛Rα｝α為X上包含R的全體同余關(guān)系.設(shè)R*=∩αRα.因為全等關(guān)系 E?R且一定是同余關(guān)系，故｛Rα｝α≠Φ.又?α，R*?Rα，從而若要c（R）=R*，只需證得R*為同余關(guān)系.由引理1可知R*為同余關(guān)系，因此c（R）= R*，命題得證.

若設(shè)C（R）為代數(shù)（X，。）上的全體同余關(guān)系，則根據(jù)定理1的證明過程可進一步得出

定理2 代數(shù)（X，。）上任意非空等價關(guān)系R是同余關(guān)系當且僅當c（R）=R.

證明 若c（R）=R，顯然R是同余關(guān)系.另一方面，若R是同余關(guān)系，且令｛Rα｝α為（X，。）上包含R的全體同余關(guān)系，則R∈｛Rα｝α.于是R?∩αRα=c（R），又R?c（R），因此c（R）=R.

定理3 設(shè)R1，R2是代數(shù)（X，。）上的兩個非空等價關(guān)系，若R1?R2，則c（R1）?c（R2）.

證明 因為R2?c（R2），且 R1?R2，故R1?c（R2）.又由于c（R2）是同余關(guān)系，故由同余閉包的定義可知c（R1）?c（R2）.

2.2商運算的定義，存在性及其粒度完備性

有了以上的鋪墊就可以比較簡捷地研究商運算的存在性問題了.給定代數(shù)（X，。）的一個等價關(guān)系 R，等價于給定了X的一個劃分，從粒計算的角度而言也就相當于給定了X的一個粒度，那么自然就會關(guān)注在新的粒度世界X/R上是否可導(dǎo)出一種代數(shù)結(jié)構(gòu)，即定義一種運算并且新的代數(shù)結(jié)構(gòu)能與原代數(shù)結(jié)構(gòu)同態(tài).代數(shù)（X，。）在保持同態(tài)性下的顆?；橇Ｓ嬎愕谋举|(zhì)要求，因為一方面可減小求解問題的規(guī)模，另一方面可使得新的結(jié)構(gòu)繼承原來結(jié)構(gòu)的一些重要性質(zhì)，從而有助于在新結(jié)構(gòu)上計算和推理.因此，研究這種運算的存在性成為了構(gòu)造粒度世界，用粒度的觀點和方法求解問題的關(guān)鍵.

定義3 設(shè)R是代數(shù)（X，。）上一個等價關(guān)系，p：X →X/R為投影.若在商空間X/R上存在運算。′，使得p是同態(tài)映射，即對?x，y∈X都有p（x。y）=p（x）?！鋚（y），則稱?！錇樯炭臻gX/R上的商運算，簡稱商運算.

對于具有多個算子的代數(shù)系統(tǒng)只需對每個算子而言投影都是同態(tài)映射即可.定義3同時說明了，如果商運算存在，那么商空間與原空間同態(tài).從而當a。x=b有解時，可得［a］?！洌踴］=［a。x］=［b］，因此［a］?！洌踴］=［b］也有解；當［a］。′［x］=［b］無解時，也就是說［a］。′［x］=［a。x］≠［b］，則a。x=b一定無解.這說明在具有代數(shù)結(jié)構(gòu)的商空間中保假原理依然成立.下面開始討論商運算的存在性.

定理4 R是代數(shù)（X，。）上的非空等價關(guān)系，則商空間X/R存在商運算的充要條件是c（R）=R.

證明 根據(jù)定理2的結(jié)論，可知原命題等價于商空間X/R存在商運算當且僅當R是同余關(guān)系.下面證明這一命題是成立的.一方面，若R是同余關(guān)系，則可定義X/R上的二元運算?！?，滿足對?x，y∈X，［x］?！洌踶］= ［x。y］.上述定義是良定的，因為：若［x1］=［x2］且［y1］=［y2］，由于R是同余關(guān)系，故［x1。y1］=［x2。y2］.因此，［x1］?！洌踶1］=［x1。y1］=［x2。y2］=［x2］。′［y2］.顯然p滿足同態(tài)性，故。′是商運算.另一方面，若商空間X/R上存在商運算?！?，則對?x，y，w，z∈X，當［x］= ［y］，［w］=［z］時，有［x。w］=p（x。w）=p（x）?！鋚（w）=［x］?！洌踳］=［y］?！洌踷］=［y。z］，因此，R是同余關(guān)系.綜上所述，命題得證.

在商空間理論中，不同粒度世界的全體構(gòu)成一個完備半序格.那么對于存在商運算的不同商空間的全體是否也構(gòu)成一個完備半序格呢？下面討論這一問題.

定義4 設(shè)R1，R2為X上的兩個非空等價關(guān)系.若R1?R2，則稱R1比R2細，或R1細于R2，記為R2≤R1或R1≥R2.

在商空間理論中用等價關(guān)系來刻畫問題的粒度，因此研究不同粒度世界之間的關(guān)系就可以從不同等價關(guān)系間的聯(lián)系入手.下面的命題給出了不同粒度世界之間的關(guān)系.

命題3［13］設(shè)R為X上全體非空等價關(guān)系，則在定義4的偏序”≤”下，（R，≤）是一個完備半序格.

命題3是商空間理論中最基本的也是最重要的定理，它為研究不同粒度世界之間的轉(zhuǎn)換，分解，合成等運算提供了理論依據(jù).本文把全體同余關(guān)系作為研究對象也得出了類似結(jié)論，即全體同余關(guān)系構(gòu)成一個完備半序格.為此，先給出如下引理.

根據(jù)等價關(guān)系的定義可很容易地得出引理2的結(jié)論.具體證明從略.引理2說明元素在算子。下的置換性具有傳遞性.

引理2 設(shè)R是代數(shù)（X，。）上的等價關(guān)系，a，b，c∈X，（a，c），（c，b）∈R.若對?x∈X，（x。a，x。c），（a。x，c。x）∈R而且（x。c，x。b），（c。x，b。x）∈R，則有（x。a，x。b），（a。x，b。x）∈R.

引理3 設(shè)C（R）是代數(shù)（X，。）上的全體同余關(guān)系，非空集合｛Rα｝α?C（R），則t（∪αRα）∈C（R）.

證明 對?x1，x2∈t（∪αRα），由于t（∪αRα）是∪αRα的 傳 遞閉包，因 此 若（x1，x2）∈∪αRα，則?Rα0∈｛Rα｝α使得（x1，x2）∈Rα0.由于Rα0是同余關(guān)系，必定滿足對?x∈X，（x。x1，x。x2），（x1。x，x2。x）∈Rα0?t（∪αRα）；否則（x1，x2）?∪αRα，由傳遞閉包的定義可知，?y1=x1，y2，…，ym=x2∈X，使得（yi，yi+1）∈∪αRα，i=1，2，…，m-1，故對每個i，?Ri∈｛Rα｝α，使得對?x ∈X，（x。yi，x。yi+1），（yi。x，yi+1。x）∈t（∪αRα）再由引理2可知，對?x∈X，（x。x1，x。x2），（x1。x，x2。x）∈t（∪αRα）.因此t（∪αRα）為同余關(guān)系，命題得證.

定理5 設(shè)（X，。）是代數(shù)，C（R）為X上全體同余關(guān)系，則在定義4的偏序”≤”下，（C（R），≤）構(gòu)成一個完備半序格.

證明 先證明∩αRα是｛Rα｝α的上確界.由引理1可知，∩αRα是同余關(guān)系.由于對?α，Rα≤∩αRα，故∩αRα是｛Rα｝α的上界.又對?R′∈C（R）且?α，R′≥Rα，即R′?Rα，則R′?∩αRα，即∩αRα≤R′，因此∩αRα為｛Rα｝α的上確界.

再證明t（∪αRα）是｛Rα｝α的下確界.由引理3知t（∪αRα）是同余關(guān)系，又對?α，Rα?t（∪αRα），即t（∪αRα）≤Rα，故t（∪αRα）是｛Rα｝α的下界.又對于?R′為｛Rα｝α的下界，即?α，R′≤Rα，有∪αRα?R′.由傳遞閉包的性質(zhì)可知，t（∪αRα）?t（R′）=R′，即R′≤t（∪αRα），因此t（∪αRα）為｛Rα｝α的下確界.綜上所述，命題得證.

在商空間理論中不同粒度世界對應(yīng)著不同等價關(guān)系，因此可知具有商運算的不同粒度世界也構(gòu)成一個完備半序格.

3 上（下）商的定義，存在性及其性質(zhì)

代數(shù)（X，。）的商空間 X/R存在商運算當且僅當R是同余關(guān)系.但是，并非任意的等價關(guān)系都是同余關(guān)系，從而并非代數(shù)（X，。）的任何商空間都存在商運算.假如X的商空間X1不存在商運算，是否可以給出一個與X1近似的且存在商運算的商空間.顯然，有兩種近似方法［13］：（1）在比X1細的所有存在商運算的商空間中是否存在最粗的商空間；（2）在比X1粗的所有存在商運算的商空間中是否存在最細的商空間X？如果有這么一個近似對（X，）存在，那么就可用它來近似描述商空間X1.可以證明這種近似對是唯一存在的.由于論域X上的一個等價關(guān)系與X的一個劃分是一一對應(yīng)的，因此可以從等價關(guān)系的角度來研究上述近似對的存在性.下面先定義上（下）同余的概念，然后以此為基礎(chǔ)來討論這種近似對的存在性.

定義5 設(shè)R是代數(shù)（X，。）上的非空等價關(guān)系.若存在同余關(guān)系ˉR≥R，且對任意同余關(guān)系R′≥R都有R′≥ˉR，則稱ˉR為R的上同余.

定義6 設(shè)R是代數(shù)（X，。）上的非空等價關(guān)系.若存在同余關(guān)系≤R，且對任意同余關(guān)系R′≤R都有≤，則稱為R的下同余.

實際上，R的上同余ˉR就是比R細的所有同余關(guān)系中最粗的同余關(guān)系，而R的下同余R是比R粗的所有同余關(guān)系中的最細的同余關(guān)系.可以證明代數(shù)（X，。）上任意等價關(guān)系R都存在上（下）同余.

定理6 設(shè)C（R）為代數(shù)（X，。）上的全體同余關(guān)系，則（X，。）的任意非空等價關(guān)系R都存在上（下）同余，且

根據(jù)定理6的結(jié)論，再結(jié)合定理2和定理4，很容易得出如下推論.具體證明從略.

推論1 代數(shù)（X，。）上任一非空等價關(guān)系R是同余關(guān)系的充要條件是

推論2 代數(shù)（X，。）在等價關(guān)系R下存在商運算的充要條件是R=ˉR和 R=R.

根據(jù)等價關(guān)系和商集的一一對應(yīng)性，再結(jié)合以上結(jié)論就可以很簡潔地討論上（下）商運算的存在性了.

定義7 設(shè)X1是代數(shù)（X，。）的一個商空間.若存在X的商空間，滿足X1≤且上存在商運算，并且對任意X′≥X1上存在商運算，都有≤X′，則稱為X的上商，相應(yīng)的商運算為X1的上商運算.

定義8 設(shè) X1是代數(shù)（X，。）的一個商空間.若存在X的商空間上存在商運算，并且對任意′≤X1上存在商運算，都有X′≤X，則稱，滿足且為X的下商，相應(yīng)的商運算為X1的下商運算.

根據(jù)等價關(guān)系與劃分的一一對應(yīng)關(guān)系，我們很容易得出代數(shù)（X，。）的任意商空間必然存在上（下）商的結(jié)論.下面以定理的形式給出，證明從略.

定理7 設(shè)X1是代數(shù)（X，。）的任意一個商空間，X1對應(yīng)的等價關(guān)系為R，則X1的上（下）商均存在，且商空間X/為X1的下商，商空間X/ˉR為R1的上商.

根據(jù)定理7的結(jié)論，可以在論域的全體等價關(guān)系上定義一對上（下）同余算子，也就是說可以在全體粒度世界上定義一對上（下）商算子.上（下）商算子可看成粒度世界中的一對近似算子，它可以把不具商代數(shù)結(jié)構(gòu)的商空間近似成具有商代數(shù)結(jié)構(gòu)的商空間.這為利用粒計算的思想，近似求解具有代數(shù)結(jié)構(gòu)的問題提供了理論基礎(chǔ).下面將給出上（下）同余算子（或商算子）的一些重要性質(zhì).

定理8 設(shè)R1，R2是代數(shù)（X，。）上的兩個非空等價關(guān)系.若R1≤R2，則

證明 （1）由于R1≤R2，則R2?R1，于是R2=，因此

定理8表明上（下）同余算子具有保序性，也就是說粒度細的商空間其上（下）商空間也細，或者說粒度粗的商空間其上（下）商空間也粗.由于不同商空間的全體構(gòu)成一個完備格，因此可以在全體商空間上定義一對格算子.下面給出一對格算子的定義，并在此格上討論上（下）商算子的一些重要性質(zhì).這些性質(zhì)為進一步研究粒度世界之間的轉(zhuǎn)換關(guān)系和粒度世界的結(jié)構(gòu)特性提供了數(shù)學基礎(chǔ).

定義9 設(shè)Q（X）是代數(shù)（X，。）上的全體商空間構(gòu)成的集合，商空間X1，X2∈Q（X），記X1∧X2，X1∨X2分別為X1，X2的下確界和上確界.

從劃分的角度來看，X1∧X2即為X1與X2的和劃分，X1∨X2為X1與X2的積劃分.因此，若X1，X2對應(yīng)的等價關(guān)系分別為R1，R2，則X1∧X2對應(yīng)的等價關(guān)系為t （R1∪R2），X1∨X2對應(yīng)的等價關(guān)系為R1∩R2.

定理9 設(shè)X1，X2是代數(shù)（X，。）上的兩個商空間，則

證明 設(shè)X1，X2對應(yīng)的等價關(guān)系分別為R1，R2，C（R）為代數(shù)（X，。）上的全體同余關(guān)系構(gòu)成的集合.

（2）由于對應(yīng)的等價關(guān)系為c（R1∩R2），則命題等價于c（R1∩R2）?c（R1）∩c（R2）.現(xiàn)在開始證明，因為R1∩R2?R1，R1∩R2?R2，由定理3知c（R1∩R2）?c（R1），c（R1∩R2）?c（R2），則c（R1∩R2）?c（R1）∩c（R2），因此對應(yīng)的等價關(guān)系為t（c（R1）∪c（R2））.X1∧X2對應(yīng)的等價關(guān)系為t（R1∪R2），故

（3）易知對應(yīng)的等價關(guān)系為c（t（R1∪R2））.于是命題等價于c（t（R1∪R2））?t（c（R1）∪（R2））.現(xiàn)在開始證明，因為R1?t（R1∪R2），R2?t（R1∪R2），由定理3知c（R1）?c（t（R1∪R2）），c（R2）?c（t（R1∪R2）），則c（R1）∪c（R2）?c（t（R1∪R2））.由傳遞閉包定義的極小性可知，關(guān)系c（R1）∪c（R2）的傳遞閉包t（c（R1）∪c（R2））是包含c（R1）∪c（R2）且滿足傳遞性的最小關(guān)系，又顯然 c（t（R1∪R2））滿足傳遞性且c（R1）∪c（R2）?c（t（R1∪R2）），故t（c（R1）∩c（R2））?c（t（R1∪R2）），因此

再證t（A∩B）?t（A）∩t（B），其中A，B為二元關(guān)系.A∩B?A，A∩B?B，則易知t（A∩B）?t（A），t（A∩B）?t（B），故t（A∩B）?t（A）∩t（B）.現(xiàn)令A(yù)=于是可得結(jié)論成立.

5）先證t（A）∪t（B）?t（A∪B），其中A，B為二元關(guān)系.A?A∪B，B?A∪B，則易知t（A）?t（A∪B），t（B）?t（A∪B），故t（A）∪t（B）?t（A∪B）.現(xiàn)令A(yù)=于是可得結(jié)論成立.

若X1，X2是代數(shù)（X，。）上兩個存在商運算的商空間，則易知商空間X1，X2的合成X3=X1∨X2也存在商運算.設(shè)X1，X2對應(yīng)的等價關(guān)系為R1，R2，則X3對應(yīng)的等價關(guān)系為R3=R1∩R2.若代數(shù)方程［a］1。1［x］1= ［b］1和［a］2。2［x］2=［b］2在各自的論域上有解（［x］i表示x關(guān)于Ri的等價類，i=1，2），又［a］3。3［x］3= ［a。x］3=［a。x］1∩［a。x］2=［b］1∩［b］2=［b］3，（其中。j表示Xj上的商運算，j=1，2，3），則可知合成空間X3=X1∨X2也有解.從而在具有代數(shù)結(jié)構(gòu)的商空間中保真原理依然成立.

4 代數(shù)商空間模型在網(wǎng)絡(luò)安全傳輸過程中的應(yīng)用

作為最重要的粒度計算模型之一，商空間模型在圖形圖像處理，海量數(shù)據(jù)挖掘和復(fù)雜問題求解等領(lǐng)域應(yīng)用廣泛.而作為商空間模型的一種重要論域結(jié)構(gòu)，代數(shù)系統(tǒng)在計算機科學中同樣應(yīng)用廣泛，如群理論和有限域理論是編碼理論的數(shù)學基礎(chǔ)；半群理論和格理論在自動機理論和形式語言中發(fā)揮了重要作用；關(guān)系代數(shù)理論成為最流行的數(shù)據(jù)庫的理論模型；格和布爾代數(shù)是電子線路設(shè)計，電子計算機硬件設(shè)計和通訊系統(tǒng)設(shè)計的重要工具［17］.

下面以糾錯碼進行傳輸?shù)穆酚蛇x擇算法為實例，分析基于代數(shù)結(jié)構(gòu)的商空間模型在網(wǎng)絡(luò)安全傳輸過程中的應(yīng)用.

二進制數(shù)字信號在網(wǎng)絡(luò)傳輸過程中，由于存在著各種干擾，可能會產(chǎn)生失真現(xiàn)象.其中一個常用的解決途徑就是采用糾錯碼傳輸，使得二進制數(shù)碼一旦在傳遞過程中出錯，接收端的糾錯碼就能立即發(fā)現(xiàn)錯誤，并將其糾正.

定義10 由0和1組成的串稱為字，一些字的集合稱為編碼，編碼中的字稱為碼字，不在編碼中的字稱為廢碼，編碼中的每個二進制信號0或1稱為碼元.

下面通過實例分析來了解編碼發(fā)現(xiàn)錯誤和糾正錯誤的能力.設(shè)有長度為2的字，當選取編碼S2=｛00，01，10，11｝時，S2中的任何一個碼字發(fā)生錯誤后還是一個碼字，故編碼S2不具有發(fā)現(xiàn)錯誤的能力.而當選取編碼C2=｛01，10｝時，因為00和11均為廢碼，當01在傳遞過程中第一個碼元由0變?yōu)?，即整個字成為11時，由于11是廢碼，故發(fā)現(xiàn)了錯誤，即編碼C2具有發(fā)現(xiàn)錯誤的能力，但它不具有糾正錯誤的能力.

設(shè)有長度為3字，選取編碼C3=｛101，010｝，則編碼C3既具有發(fā)現(xiàn)錯誤又具有糾正錯誤的能力.因為碼字101出現(xiàn)單個錯誤后將變?yōu)椋?01，111，100；而碼字010出現(xiàn)錯誤后將變?yōu)?10，000，011.故如碼字101在傳遞過程中任何一個碼元出現(xiàn)了錯誤，整個碼字只會變?yōu)?11，100或001，但是都可知其原碼為101.但顯然，C3僅能發(fā)現(xiàn)單個錯誤.

定義11 設(shè)Sn是長度為n的字集，即Sn=｛a1a2…an|ai=0或1，i=1，2，…，n｝，其中X，Y∈Sn，X=x1x2…xn，Yn=y1y2…yn，則在Sn上定義二元運算。為：Z=X。Y =z1z2…zn，其中zi=xi+2yi（i=1，2，…，n），運算符+2為模2加運算（即0+21=1+20=1，0+20=1+21= 0），稱運算。為按位加運算.

顯然，＜Sn，。＞是一個代數(shù)系統(tǒng).并且運算 。滿足結(jié)合律，它的幺元為00…0，每個元素的逆元都是它自身，因此，＜Sn，。＞是一個群.事實上，在糾錯碼理論中還有描述兩個編碼之間相似度的漢明距離的公式表示，一個編碼發(fā)現(xiàn)單個錯誤和多個錯誤能力的充要條件的論證等，在此不再贅述.

以上分析說明，以糾錯碼進行傳輸?shù)臄?shù)據(jù)，其數(shù)據(jù)之間是一種如定義11所示的代數(shù)結(jié)構(gòu)，即按位加運算.

隨著網(wǎng)絡(luò)的不斷增大和動態(tài)更新，路由器路由選擇表會急速增大，路由器之間路由表及其更新信息的傳輸量也會急速增大，且傳輸過程中數(shù)據(jù)容易出錯［18，20］.因此，文中對路由表信息的編碼采用糾錯碼，對路由的選擇也不得不引入分級（不同粒度）的概念.

對于互聯(lián)網(wǎng)這樣的網(wǎng)絡(luò)，僅分兩級是不夠的，有必要將區(qū)域分組.目前常用的做法是先形成簇，簇又分成區(qū)，區(qū)再分成組，以此法繼續(xù)下去（見圖1）.這種分組法正是商空間模型應(yīng)用的典型實例.在分組法的不同粒度世界中，簇的粒度最粗，組的粒度最細.

對一個龐大的網(wǎng)絡(luò)，不同粒度的簇，區(qū)和組的確定方法有所不同.因為路由表信息是由具有代數(shù)結(jié)構(gòu)的糾錯碼表示，為了保持不同粒度之間轉(zhuǎn)換時的保假，保真原理成立，在確定其粒度層次時，我們必須以具有特定屬性的同余關(guān)系來劃分等價類.那么，一個大型網(wǎng)絡(luò)，到底需要分為幾種粒度呢.這可引用Kamoun和Kleinrock的結(jié)論［16］，他們發(fā)現(xiàn)有N個路由器的子網(wǎng)的最優(yōu)級數(shù)為lnN，其中每個路由器需要的表項總數(shù)為elnN.

從上述的討論可知，復(fù)雜網(wǎng)絡(luò)中的路由可歸結(jié)為粒計算理論中具有代數(shù)結(jié)構(gòu)的商空間模型的應(yīng)用.

5 結(jié)論

在基于商空間的粒計算模型中粒度構(gòu)造是通過等價關(guān)系（劃分）來完成的，所以不同的等價關(guān)系就對應(yīng)著問題的不同粒度［14］，從而可以通過分析不同等價關(guān)系間的聯(lián)系來研究不同粒度世界間的關(guān)系.因此，從等價關(guān)系的角度來研究具有代數(shù)結(jié)構(gòu)的商空間模型就十分自然，也比較簡便［19］.對于具有代數(shù)結(jié)構(gòu)的問題（X，。），給定其上一個等價關(guān)系R，并不一定可以得到它的一個商空間，因為這個等價關(guān)系沒有考慮到問題的結(jié)構(gòu).要想獲得原問題的一個商空間就必須考慮問題的結(jié)構(gòu)，即對等價關(guān)系加以約束.由此也可看出結(jié)構(gòu)因素是非常重要的，它在商空間模型中扮演著重要的角色［15］，一方面它增強了商空間的表達能力，另一方面也增添了問題?；膹?fù)雜性.在具有代數(shù)結(jié)構(gòu)的商空間模型中與問題粒度一一對應(yīng)的不是一般的等價關(guān)系，而是比等價關(guān)系更強的同余關(guān)系.由于全體同余關(guān)系仍然構(gòu)成一個完備半序格，因此在具有代數(shù)結(jié)構(gòu)的商空間模型中粒度世界的結(jié)構(gòu)仍然具有完備性.另外，由于此處在商空間的構(gòu)造中本身就遵循了同態(tài)原則，因此保假，保真原理在具有代數(shù)結(jié)構(gòu)的商空間模型中依然成立.這些結(jié)論說明了在具有代數(shù)結(jié)構(gòu)的商空間模型中商空間理論的基本結(jié)論依然成立.本文還從關(guān)系的角度引入了對應(yīng)于上（下）商概念的上（下）同余，從論證的過程可以看出從關(guān)系的角度來證明上（下）商的存在性相比文獻［13］中的方式更為簡捷.在現(xiàn)有商空間模型中問題描述模式（X，f，T）的T一般指定為拓撲結(jié)構(gòu)，而代數(shù)結(jié)構(gòu)也是一種常見的和十分重要的論域結(jié)構(gòu)，因此從這個角度而言，本文擴展了現(xiàn)有商空間模型，也為商空間理論和相關(guān)代數(shù)理論的結(jié)合奠定了基礎(chǔ).

［1］Yao Y Y.Granular computing［A］.Proceedings of the 4th Chinese National Conference on Rough Sets and Soft Computing［C］.Chongqing：Computer Science，2004.1-5.

［2］Pedrycz W.Granular computing-the emerging paradigm ［J］.Journal of Uncertain Systems，2007，1（1）：38-61.

［3］Yao Y Y.The rise of granular computing［J］.Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition），2008，20（3）：299-306.

［4］F Deng，H Pan.Research of intrusion detection system model based on granular computing［J］.Modern Electronics Technique，2011，34（10）：115-117.

［5］王國胤，張清華，胡軍.粒計算研究綜述［J］.智能系統(tǒng)學報，2007，2（6）：8-26. Wang GuoYing，Zhang QingHua，Hu Jun.An overview of granular computing［J］.CAAI Transactions on Intelligent Systems，2007，2（6）：8-26.（in Chinese）

［6］Zhang Xianyong，Miao Duoqian.Quantitative information architecture，granular computing and rough set models in the double-quantitative approximation space of precision and grade［J］.Information Sciences，2014，6（268）：147 -168.

［7］Yao Yiyu.Granular computing：past，present and future ［A］.Proc of the IEEE International Conference on Granular Computing［C］.Hangzhou，China，2008.80-85.

［8］張燕平，張鈴，吳濤.不同粒度世界的描述法-商空間法［J］.計算機學報，2004，27（3）：328-333. Zhang YanPing，Zhang Ling，Wu Tao.The representation of different granular worlds-a quotient space［J］.Chinese Journal of Computers，2004，27（3）：328-333.（in Chinese）

［9］李道國，等.粒度計算研究綜述［J］.計算機科學，2005，32 （9）：1-12. Li DaoGuo，et al.An overview of granular computing［J］. Computer Science，2005，32（9）：1-12.（in Chinese）

［10］王向陽，張燕平.粒度計算中的商結(jié)構(gòu)［J］.計算機技術(shù)與發(fā)展，2008，18（1）：111-118. Wang Xiang-Yang，Zhang Yan-Ping.The quotient structure in granule computing［J］.Computer Technology and Development，2008，18（1）：111-118.（in Chinese）

［11］Wang J，Zhou J.Research of reduct features in the variable precision rough set model［J］.Neurocomputing，2009，72 （10）：2643-2648.

［12］Jing Tao Yao，Vasilakos A V，Pedrycz W.Granular computing：perspectives and challenges［J］.IEEE Transactions on Cybernetics，2013，43（6）：1977-1989.

［13］張鈴，張鈸.問題題求解理論及應(yīng)用（第二版）［M］.北京：清華大學出版社，2007. Zhang Lin，Zhang Bo.Theory and Applications of Problem Solving（Second edition）［M］.Beijing：Tsinghua University Press，2007.（in Chinese）

［14］Zhang Ling，Zhang Bo.The quotient space theory of problem solving［J］.Fundamenta Informatcae，2004，59（2）：287-298.

［15］Zhao LiQuan，et al.Research in quotient space theory based on structure［A］.Proceeding of IEEE International Conference on Cognitive Informatics［C］.Beijing，2006. 309-313.

［16］Kamoun D，Kleimrock L.Stockastic Performance Evaluation of Hierarchical Routing for Large Networks［M］. Computer Networks，1979，3（5）：337-353.

［17］Wang Shengsheng，LIU Dayou.An effcient method for calculating qualitative spatial relations［J］.Chinese Journal of Electronics，2009，18（1）：42-46.

［18］Wang Chengyao，Zheng Xuefeng.Service oriented dynamic coordination method based on role for multi-level hierarchical information systems［J］.Chinese Journal of Electronics，2013，22（2）：253-257.

［19］王加陽，楊正華.兩種結(jié)構(gòu)的商空間模型比較研究［J］.電子學報，2013，41（11）：2262-2269. Wang Jiayang，Yang Zhenghua.A comparative study of quotient space model with two structures［J］.Acta Electronica Sinica，2013，41（11）：2262-2269.（in Chinese）

［20］賈杰，等.無線傳感器網(wǎng)絡(luò)中聯(lián)合路由優(yōu)化的高能效鏈路調(diào)度［J］.電子學報，2014，42（6）：1118-1124. Jia Jie，et al.Energy-Efficient link scheduling combined with routing optimization in wireless sensor network［J］. Acta Electronica Sinica，2014，42（6）：1118-1124.（in Chinese）

陳林書 男，1981年生，湖南平江人.講師，博士研究生.2007年于中南大學計算機應(yīng)用專業(yè)碩士畢業(yè)，后進入湖南科技大學計算機學院工作，主要研究方向為粒計算與智能信息處理.

E-mail：chen-lin-shu@163.com

王加陽 男，1963年出生于湖南長沙，中南大學信息科學與工程學院教授，博士生導(dǎo)師，主要研究方向為智能計算與信息融合.

E-mail：csuwjy@163.com

A Study for Quotient Space Model Based on Algebraic Structure

CHEN Lin-shu1，2，WANG Jia-yang1，YANG Zheng-hua1，LI Li3

（1.School of Information Science and Engineering，Central South University，Changsha，Hunan 410083，China）2.School of Computer Science and Engineering，Hunan University of Science and Technology，Xiangtan，Hunan 411201，China；3.Harbin Institute of Technology Shenzhen Graduate School，Shenzhen，Guangdong 518055，China）

The domain structure in the existing QSM（quotient space model）is usually a topology，and a granule is uniquely determined by an equivalence relation.However，when the domain structure is assumed as a widely used algebra instead of a topology，it introduces the concept of congruence relation，and systematically demonstrates the existence of two basic conclusions in QSM based on algebraic structure—all the congruence relations forming a complete semi-order lattice and the principles of falsity preserving and truth preserving.And when the equivalence relation determining a granule is not a congruence relation，it defines the concepts of least upper（greatest lower）congruence and least upper（greatest lower）quotient in antithesis，proves their existence for simplicity，and discusses some of their important properties which are the theoretical basis for the composition and decomposition of different granularities.Finally，based on the routing algorithm transmitting as error correcting codes，it analyzes the application of QSM based on algebraic structure during network secure transmission.The paper extends the theory of QSM from structure，and provides theoretical basis for the combination of quotient space theory and algebraic theory.

granular computing；quotient space；congruence closure；quotient operation；least upper（greatest lower）quotient

TP18

A

0372-2112（2016）04-0952-07

電子學報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.028

2014-07-15；

2014-12-08；責任編輯：李勇鋒

國家自然科學基金（No.61173052）；湖南省自然科學基金（No.14JJ4007）