網(wǎng)絡(luò)編碼錯(cuò)誤空間與信息空間交空間的維數(shù)

劉海波， 廖群英

（四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院，四川 成都610066）

1 預(yù)備知識(shí)

網(wǎng)絡(luò)編碼（Network Coding）是由 Yeung等［1］提出，隨后由Ahlswede等［2］進(jìn)一步發(fā)展起來．因?yàn)榫W(wǎng)絡(luò)編碼能顯著地提高信息的傳輸效率，所以一直是近年來的研究熱點(diǎn)，尤其對(duì)無錯(cuò)誤發(fā)生的網(wǎng)絡(luò)，可參見文獻(xiàn)［3－10］．遺憾的是在實(shí)際網(wǎng)絡(luò)傳輸中會(huì)出現(xiàn)許多種類的錯(cuò)誤．為應(yīng)對(duì)這種問題，學(xué)者們提出了網(wǎng)絡(luò)糾錯(cuò)編碼（Network Error Correction Coding），參見文獻(xiàn)［11－13］．事實(shí)上，網(wǎng)絡(luò)糾錯(cuò)碼可以看作經(jīng)典糾錯(cuò)碼的推廣，即在經(jīng)典糾錯(cuò)碼里的某些界都可以推廣到網(wǎng)絡(luò)糾錯(cuò)碼中，例如Singleton界、Hamming界和 Gilbert－Varshamov界［11－12］．達(dá)到Singleton界的線性網(wǎng)絡(luò)糾錯(cuò)碼稱為線性網(wǎng)絡(luò)極大距離可分碼，簡稱為網(wǎng)絡(luò)MDS碼．作為一類好的網(wǎng)絡(luò)糾錯(cuò)碼，網(wǎng)絡(luò)MDS碼無論在理論研究還是在現(xiàn)實(shí)應(yīng)用中都有著重要的地位，參見文獻(xiàn)［14］．

在實(shí)際的網(wǎng)絡(luò)通訊中，需要信源通過不同的信息率傳遞不同的信息．在這種情況下，考慮到糾錯(cuò)的情形，Guang等［15］構(gòu)造一類變率的網(wǎng)絡(luò) MDS碼，這其中涉及到對(duì)網(wǎng)絡(luò)MDS碼信息空間與達(dá)到最小距離的錯(cuò)誤空間的交空間的維數(shù)刻化．本文將進(jìn)一步刻化一般網(wǎng)絡(luò)糾錯(cuò)碼的信息空間與達(dá)到最小距離錯(cuò)誤空間的交空間的維數(shù)；在給定錯(cuò)誤模式的前提下，給出網(wǎng)絡(luò)MDS碼信息空間與該錯(cuò)誤模式所生成的錯(cuò)誤空間的交空間的維數(shù)的界．

接下來介紹相關(guān)的概念與記號(hào)．通訊網(wǎng)絡(luò)是定義在有限非循環(huán)的有向圖G＝（V，E）上的，其中V表示點(diǎn)集，E表示邊集．點(diǎn)集V由不相交的3部分S、T以及J構(gòu)成，其中S是信源節(jié)點(diǎn)集，T是信宿節(jié)點(diǎn)集，J＝V＼（S∪T）是中間節(jié)點(diǎn)集．

有向邊e＝（i，j）∈E表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j，節(jié)點(diǎn)i與j稱為邊e的尾與頭，記作i＝tail（e），j＝head（e）．邊e稱為i輸出信道，j的輸入信道．給定節(jié)點(diǎn)i，記Out（i）為i的輸出信道集，In（i）為i的輸入信道集．

本文中考慮的是｜S｜＝1的情形，即有唯一的信源節(jié)點(diǎn)s．顯然信源節(jié)點(diǎn)s沒有輸入信道，信宿節(jié)點(diǎn)沒有輸出信道，為敘述方便，對(duì)信源節(jié)點(diǎn)s引入虛擬輸入信道．假設(shè)s單位時(shí)間內(nèi)傳輸ω個(gè)域F上的元素X＝［X1X2…Xω］，則信源節(jié)點(diǎn)s有ω個(gè)虛擬輸入信道d′1，d′2，…，d′ω，即

令Ue為信道e上傳遞的ω－維的向量，則在信源節(jié)點(diǎn)s，有Ud′i＝Xi（1≤i≤ω）．在節(jié)點(diǎn)i∈V＼T，稱｜In（i）｜×｜Out（i）｜矩 陣 Ki＝ ［kd，e］d∈In（i），e∈Out（i）為節(jié)點(diǎn)i的局部編碼矩陣，其中kd，e∈F為相鄰信道（d，e）局部編碼系數(shù)．對(duì)于e∈E上傳遞的信息Ue，可以由如下的式子迭代得到易見Ue是ω個(gè)向量Xi（1≤i≤ω）的線性組合．若存在F上ω維的列向量fe，滿足Ue＝X·fe，則稱fe為信道e的全局編碼系數(shù)［6－7］，即

當(dāng)有錯(cuò)誤發(fā)生在信道e上時(shí)，記錯(cuò)誤為Ze∈F，則信道e的輸出為珦Ue＝Ue＋Ze．特別地，將Ze視作信息稱為錯(cuò)誤信息，定義｜E｜－維的錯(cuò)誤向量為Z＝［Ze：e∈E］．對(duì)于信道e∈E，存在虛擬信道e′與e的尾相連，提供錯(cuò)誤信息Ze．為了區(qū)分虛擬信道，稱d′i（1≤i≤ω）為虛擬信息信道，e′∈E′為虛擬錯(cuò)誤信道．稱珟G＝（珟V，珟E）為G擴(kuò)展網(wǎng)絡(luò)，其中珟V＝V，珟E＝E∪E′∪｛d′1，d′2，…，d′ω｝，E′＝｛e′：e∈E｝．令ke′，e＝1，對(duì)于d∈E／｛e｝，kd，e＝0，則G 上線性網(wǎng)絡(luò)編碼可以擴(kuò)展到珟G上．類似地，對(duì)于e∈珟E，可以定義擴(kuò)展的全局編碼系數(shù)珟fe，以及線性的網(wǎng)絡(luò)糾錯(cuò)碼．

定義1．1［15］F上ω－維的線性網(wǎng)絡(luò)糾錯(cuò)碼是由滿足如下條件的擴(kuò)展的全局編碼系數(shù)構(gòu)成：

1）當(dāng)1≤i≤ω時(shí)，珟fd′i＝1d′i；當(dāng)e′∈E′時(shí)，珟fe′＝1e，其中1d（d∈In（s）∪E）為（ω＋｜E｜）－維的列向量的指標(biāo)函數(shù)．

2）對(duì)于其他e∈E，

其中kd，e∈F為相鄰信道（d，e）的局部編碼系數(shù)．

在信宿節(jié)點(diǎn)t∈T，令rowt（d）為解碼矩陣

中被指標(biāo)d∈In（s）∪E所確

定｜In（t）｜－維的行向量．錯(cuò)誤模式ρ為某些信道的集合，即ρE，稱錯(cuò)誤信息Z＝［Ze：e∈E］匹配錯(cuò)誤模式ρ是指對(duì)于e∈E／ρ，Ze＝0．對(duì)于錯(cuò)誤模式ρ，以及t∈T，定義錯(cuò)誤空間Δ（t，ρ）＝｛（0Z）珟Ft＝Z·Gt：Z∈ F｜E｜匹配ρ｝，以及信息空間 Φ（t）＝｛（X0）＝X·Ft：X∈Fω｝．記其中，L表示向量的集合，〈L〉由L中所有向量生成的子空間．

定義1．2［14］對(duì)于線性網(wǎng)絡(luò)糾錯(cuò)碼，在信宿節(jié)點(diǎn)t∈T的最小距離定義為其中｜ρ｜記為錯(cuò)誤ρ的階．

引理1．3［14］（Singleton界） 令d（t）min為線性網(wǎng)絡(luò)糾錯(cuò)碼在信宿節(jié)點(diǎn)t∈T的最小距離，則其中，Ct為信源節(jié)點(diǎn)s與信宿節(jié)點(diǎn)t的最小割，ω為信息率，δt＝Ct－ω為信宿節(jié)點(diǎn)t的冗余．

達(dá)到這個(gè)界的網(wǎng)絡(luò)糾錯(cuò)碼稱為網(wǎng)絡(luò)MDS碼．對(duì)于網(wǎng)絡(luò)MDS碼與達(dá)到最小距離錯(cuò)誤空間的交空間的維數(shù)，Guang等［15］給出了如下刻化：

引理1．4［15］設(shè)Cω為G 上ω－維的網(wǎng)絡(luò) MDS碼，則對(duì)于任意的信宿節(jié)點(diǎn)t以及錯(cuò)誤模式ρ∈Q（t）有

2 主要結(jié)果及證明

本節(jié)給出本文的主要結(jié)果及證明，即定理2．1和2．2．定理2．1將文獻(xiàn)［15］中結(jié)果推廣到一般的網(wǎng)絡(luò)糾錯(cuò)碼．在給定錯(cuò)誤模式的前提下，定理2．2給出其錯(cuò)誤空間與網(wǎng)絡(luò)MDS碼信息空間的交空間維數(shù)的界．

定理2．1 設(shè)Cω為G上ω－維網(wǎng)絡(luò)糾錯(cuò)碼，則對(duì)于任意的信宿節(jié)點(diǎn)t∈T以及錯(cuò)誤模式ρ∈Q（t）有

令r1，r2，…，rd為Δ （t，ρ）中d 個(gè)線性無關(guān)向量，即．假設(shè)dimΔ（ （t，ρ）∩Φ（t））≥2，令珒l1、珒l2為交空間Δ（t，ρ）∩Φ（t）中的2個(gè)線性無關(guān)的向量，則在F存在兩組不全為0的數(shù)組a1，a2，…，ad與b1，b2，…，bd滿足對(duì)于i＝1，2，…，d，ai或者bi中一定有一個(gè)為0，否則，若存在某個(gè)i（1≤i≤d）滿足ai≠0，bi≠0，即有

且ail2－bil1≠0．故

這也與d（t）min＝d矛盾．

綜上，對(duì)于任意的ρ∈Q（t），有

對(duì)網(wǎng)絡(luò)MDS碼Cω，在信宿節(jié)點(diǎn)t∈T定義錯(cuò)誤模式的集合為

其中1≤i≤｜E｜－δt．對(duì)于任意的信宿節(jié)點(diǎn)t∈T以及錯(cuò)誤模式ρ∈Qi（t），如下的定理2．2給出的界．

定理2．2 設(shè)Cω為G上ω－維網(wǎng)絡(luò)MDS碼，則對(duì)任意的信宿節(jié)點(diǎn)t∈T以及錯(cuò)誤模式ρ∈Qi（t），有

證明 對(duì)i用數(shù)學(xué)歸納法．當(dāng)i＝1時(shí)，由引理1．4即得．假設(shè)當(dāng)i＝k－1（k＞1）時(shí)，結(jié)論成立．

當(dāng)i＝k 時(shí)，注意到 Qk（t）＝Qk－1（t）∪ ｛ρ：則只需證明對(duì)于任意信宿節(jié)點(diǎn)t∈T，以及錯(cuò)誤模式ρ∈Qk（t）且，滿足即可．事實(shí)上，對(duì)于任意，由（1）式有．另一方面，根據(jù)定義1．2，有因此，對(duì)于任意的有為敘述方便，記，其中．令為Δ （t，ρ）中d 個(gè)線性無關(guān)的向量，即

所以，對(duì)于1≤j≤k＋1，由于存在某些aj，1＝0，不失一般性，對(duì)于1≤c≤d，假設(shè)c）且如若不然可以調(diào)整d個(gè)向量r1，r2，…，rd的順序．對(duì)于1≤j≤c，有珒lj∈，即對(duì)于，由有

由歸納假設(shè)，知k個(gè)向量珒lj（j＝1，2，…，c），

中線性相關(guān)的，即存在不全為0的b1，…，bk∈F，滿足

等價(jià)于

這就證明了定理2．2．