胡國香,張煥國
?
VI-2類5維元線性碼的漢明重量譜的確定
胡國香1,2,張煥國1
(1. 武漢大學(xué)計(jì)算機(jī)學(xué)院,湖北武漢 430072;2. 中南民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院,湖北武漢 430074)
上線性碼的漢明重量譜為序列,其中,d是的維子碼的最小支撐重量。第VI類5維元線性碼的漢明重量譜,按照新的必要條件可以分成6個(gè)子類。運(yùn)用有限射影幾何方法研究VI-2類的5維元線性碼的漢明重量譜,確定VI-2類5維元線性碼的幾乎所有漢明重量譜。
漢明重量;線性碼;差序列;射影幾何
通信系統(tǒng)中信息的傳遞離不開編碼,而漢明重量是編碼理論中非常重要的基本概念,與編碼中碼的檢錯(cuò)以及糾錯(cuò)能力息息相關(guān)。編碼理論的創(chuàng)始人之一漢明(Hamming)提出了漢明重量。廣義漢明重量最初是由用于第2類竊密信道的線性編碼方案所觸動(dòng)而提出的。假設(shè)發(fā)送者有bit信息被編成bit碼后通過此信道傳送給接收者。入侵者能夠從信道碼中隨意竊取到其中的bit數(shù)據(jù)。傳送的信道假設(shè)是無噪的,因而正確譯碼沒有問題。問題的焦點(diǎn)是如何阻止入侵者獲太多的信息,也就是設(shè)計(jì)出一種編碼方案,使入侵者截取bit數(shù)據(jù)時(shí),對(duì)于數(shù)據(jù)的可疑度(不確定度)盡可能得大。事實(shí)上,當(dāng)一種線性碼用于上述信道時(shí),廣義漢明重量可以完全表現(xiàn)出該碼的特性。線性碼的廣義漢明重量譜是Wei[1]首次正式提出的,廣義漢明重量是碼的最小距離的推廣。線性碼是編碼理論中一類非常重要的碼,很多其他形式的碼都可以和線性碼找到一定的聯(lián)系。漢明重量的另一種形式被Forney稱作長度/維數(shù)輪廓,在線性碼的格子復(fù)雜度分析[2~6]、譯碼分析[7~9]、檢錯(cuò)分析[10]等方面都有非常重要的應(yīng)用,文獻(xiàn)[11]也詳細(xì)討論了其應(yīng)用。重量譜的概念由Wei提出以后,立即成為編碼理論的一個(gè)前沿研究熱點(diǎn)。
1.1 基礎(chǔ)知識(shí)
對(duì)于一個(gè)碼,中的所有碼字的非零位置的全體所構(gòu)成的集合稱為的支撐集,記為,即,支撐集的大小記為。
“如何確定線性碼的漢明重量譜”一直是編碼理論研究的核心問題。關(guān)于漢明重量譜的研究,第1個(gè)研究方向是關(guān)于具體的各類線性糾錯(cuò)碼的。由于確定是編碼理論中尚未完全解決的難題,因此的確定更加困難,目前僅有少數(shù)的幾類碼確定了重量譜。文獻(xiàn)[12]確定了RM碼、漢明碼及其補(bǔ)碼、擴(kuò)展?jié)h明碼、極大距離可分碼等的重量譜;文獻(xiàn)[13~15]對(duì)廣義漢明重量的上下限進(jìn)行了研究;文獻(xiàn)[16,17]中,重量譜的類別被擴(kuò)展到線性等重碼。第2個(gè)方向是關(guān)于一般線性碼的。對(duì)于一般線性碼的重量譜,傳統(tǒng)的研究方法有組合方法與計(jì)算機(jī)搜索。但是隨著線性碼維數(shù)的增加,重量譜的類別也呈指數(shù)增加,對(duì)于高維數(shù)線性碼重量譜的研究更加困難,這2種方法均不太適用。目前來看,有限射影幾何方法對(duì)于高維數(shù)線性碼重量譜的研究較為適用。
1.2 相關(guān)工作
1992年,密碼學(xué)家Helleseth[18]提出了確定一般線性碼的所有可能的漢明重量譜,這也是編碼理論中一個(gè)非常有意義的理論問題。1996年,陳文德等[19]提出了有限射影幾何方法,并第一次有效地用于確定4維元線性碼的漢明重量譜。他們還把4維元線性碼及其漢明重量譜分成了9類,用有限射影幾何方法取得了豐富的分類研究成果,參見文獻(xiàn)[20,21]等。文獻(xiàn)[22]對(duì)4維元線性碼的漢明重量譜進(jìn)行研究,確定4維元線性碼的幾乎所有的漢明重量譜。文獻(xiàn)[23]中把5維元線性碼及其漢明重量譜分成6類,并對(duì)6類碼中的II-1類進(jìn)行了研究;文獻(xiàn)[24]對(duì)II-2類進(jìn)行了研究。文獻(xiàn)[25]確定了5維元線性碼V-1類的幾乎所有的漢明重量譜。文獻(xiàn)[26]確定了5維元線性碼V-2類的幾乎所有的漢明重量譜。在文獻(xiàn)[27]中第VI類5維元線性碼的漢明重量譜又被分成了6個(gè)子類,并對(duì)其中的VI-1類進(jìn)行研究,確定該類的幾乎所有的漢明重量譜。本文將對(duì)文獻(xiàn)[27]中的VI-2子類進(jìn)行研究,并確定其幾乎所有的漢明重量譜。
本文主要研究了文獻(xiàn)[27]中5維元線性碼的第VI-2類的漢明重量譜。利用有限射影幾何方法,通過往4維空間進(jìn)行投影,把重量譜的確定轉(zhuǎn)化為4維空間中的點(diǎn)、線、面、體的賦值函數(shù)的確定問題,使確定重量譜這一抽象的理論問題變得更為形象化。
(1)
文獻(xiàn)[27]中把5維元線性碼的第VI類的差序列的必要條件分成6個(gè)子類,并對(duì)其中的VI-1類進(jìn)行了研究,其他5個(gè)子類的重量譜均未確定。相比VI-1類來說,VI-2重量譜的確定更為困難,因?yàn)楫?dāng)取得上界時(shí),賦值函數(shù)的取值不完全為的整數(shù)倍,需要考慮將進(jìn)行分?jǐn)?shù)化處理。
本文研究這6類中的VI-2個(gè)子類。由文獻(xiàn)[27]可得VI-2類差序列的必要條件如下。
下面將構(gòu)造出VI-2類的幾乎所有可能的漢明重量譜,即證明上述必要條件是幾乎充分的,以下的引理1~引理4將給出各種條件下的詳細(xì)證明與賦值函數(shù)的構(gòu)造。
引理1 設(shè)
(3)
(4)
證明 把式(2)~式(5)代入后,得
定義下面這些符號(hào)為
點(diǎn)、線、面、體之間的關(guān)系說明如下。
證明 定義以下一些符號(hào)(如圖2所示)。
所以可令
證明 先定義以下一些符號(hào)(如圖3所示)。
1) 由點(diǎn)的非負(fù)性,可得
又由
又由
又由
又由
3)由面之間的關(guān)系可得
又由
1) 由點(diǎn)的非負(fù)性,可得
又由
3) 由面之間的關(guān)系,可得
又由
所以,
由上述引理1~引理4,可得如下的定理。
所以,由引理1~引理4,該定理的充分性得證,也就得到了VI-2類的幾乎所有的差序列。
本文對(duì)5維元線性碼中的第VI-2類進(jìn)行研究,運(yùn)用有限射影幾何方法通過對(duì)射影空間中的點(diǎn)進(jìn)行賦值,得到不同條件下賦值函數(shù)的構(gòu)造,從而得到第VI-2類5維元線性碼的幾乎所有的漢明重量譜。
[1] WEI V K. Generalized Hamming weight for liner codes[J]. IEEE Transactions Information Theory, 1991,37(5):1412-1418.
[2] FORNEY G D. Dimension/length profiles and trellis complexity of liner block codes[J]. IEEE Transactions Information Theory, 1994, 40(6):1741-1752.
[3] KASAMI T, TAKATA T, FUJIWARA T, et al. On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes[J]. IEEE Transactions Information Theory, 1993, 39(1): 242-245.
[4] MORELOS-ZARAGOZA R, FUJIWARA T, KASAMI T, et al. Constructions of generalized concatenated codes and their trellis-based decoding complexity[J]. IEEE Transactions Information Theory, 1999, 45(2): 725-731.
[5] SHANY V, BE’ERY Y. The preparata and goethals codes: trellis complexity and twisted squaring constructions[J]. IEEE Transactions Information Theory, 1999, 45(5): 1667-1673.
[6] VARDY A, BE’ERY Y. Maximum-likelihood soft decision decoding of BCH codes[J]. IEEE Transactions Information Theory, 1994, 40(2): 546-554.
[7] FOSSORIER M P C, LIN S. A unified method for evaluating the error-correction radius of reliability-based soft-decsion algorithms for linear block codes[J]. IEEE Transactions Information Theory, 1998, 44(2): 691-700.
[8] FOSSORIER M P C, LIN S, SNYDERS J. Reliability-based syndrom decoding of linear block codes[J]. IEEE Transactions Information Theory, 1998, 44(1): 388-398.
[9] GAZELLE D, SNYDERS J. Reliability-based code-search algorithms for maximum-likelihood decoding of block codes[J]. IEEE Transactions Information Theory, 1997, 43(1):239-249.
[10] KL?VE T. The worst-case probability of undetected error for linear codes on the local binomial channel[J]. IEEE Transactions Information Theory, 1996, 42(1): 172-179.
[11] 岳殿武,酆廣增.廣義Hamming重量,維數(shù)/長度輪廓及其應(yīng)用[J].電子學(xué)報(bào),1999,27(4):111-115.
YUE D W, FENG G Z. Generalized Hamming weight, dimension/length profile and their applications[J]. Chinese Journal of Electronics, 1999, 27(4):111-115.
[12] 羅守山,陳萍,楊義先.廣義漢明重量下限函數(shù)L()的新證明[J].北京郵電大學(xué)學(xué)報(bào),1996,19(4):67-70.
LUO S S, CHEN P, YANG Y X. A new proof of lower boundL() of generalized Hamming weights[J]. Beijing University of Posts and Telecommunications, 1996,19(4):67-70.
[13] 羅守山,楊義先,吳偉陵.線性碼廣義漢明重量的上限函數(shù)[J].通信學(xué)報(bào), 1999,20(11):86-90.
LUO S S, YANG Y X, WU W L.The upper bound of generalized Hamming weight of linear codes[J]. Journal on Communications, 1999, 20(11):86-90.
[14] 岳殿武,胡正名.廣義Hamming重量上/下界的對(duì)偶定理[J].通信學(xué)報(bào),1997,18(7):76-78.
YUE D W, HU Z M. A dual theorem of upper and lower bounds on the generalized Hamming weights[J]. Journal on Communications, 1997, 18(7):76-78.
[15] 岳殿武,胡正名.關(guān)于BCH碼的廣義Hamming重量上下限[J].通信學(xué)報(bào),1997,18(4):75-79.
YUE D W, HU Z M. Upper bounds and lower bounds on generalized Hamming weight for BCH codes[J]. Journal of Communications, 1997, 18(4):75-79.
[16] 岳殿武,胡正名.廣義Hamming重量和等重碼[J].電子科學(xué)學(xué)刊, 1997,19(4):553-557.
YUE D W, HU Z M. Generalized Hamming weights and equal weight codes[J]. Journal of Electronics, 1997,19(4):553-557.
[17] 岳殿武,江凌云,段冰娟.線性等重碼格子復(fù)雜度的確定[J].應(yīng)用科學(xué)學(xué)報(bào),2000,18(1):68-71.
YUE D W, JIANG L Y, DUAN B J. The determination of trellis complexity of linear constant weight codes[J]. Journal of Applied Sciences, 2000,18(1):68-71.
[18] HELLESETH T, KL?VE T , YTREHUS ?. Generalized Hamming weights of linear codes[J]. IEEE Transactions Information Theory, 1992, 38(3): 1133-1140.
[19] CHEN W D, KL?VE T. The weight hierarchies of-ary codes of dimension 4[J]. IEEE Transactions Information Theory, 1996, 42(7): 2265-2272.
[20] CHEN W D, KL?VE T. Bounds on the weight hierarchies of linear codes of dimension 4[J]. IEEE Trans Inform Theory, 1997, 43(6): 2047-2054.
[21] CHEN W D, KL?VE T. The weight hierarchies of-ary codes of dimension 4[J]. IEEE Transactions Information Theory, 1996, 42(7):2265-2272.
[22] HU G X, CHEN W D. The weight hierarchies of q-ary linear codes of dimension 4[J]. Discrete Mathematics, 2010, 310(24):3528-3536.
[23] 王麗君,陳文德.5維元線性碼重量譜的分類與確定[J].系統(tǒng)科學(xué)與數(shù)學(xué),2011,31(4):402-413.
WANG L J, CHEN W D. The classification and determination on weight hierarchies of-ary linear codes of dimension 5[J]. Journal of Systems Science and Complexity, 2011, 31(4): 402-413.
[24] 王麗君, 陳文德.II2類5維元線性碼的重量譜[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2011, 41(21): 244-252.
WANG L J, CHEN W D.MathematicsinPracticeandTheory, 2011, 41(21):244-252.
[25] 王麗君,陳文德.一類5維元線性碼重量譜的確定[J].科學(xué)通報(bào),2011,56(25):2150-2155.
WANG L J, CHEN W D.
[26] 王麗君,陳文德. V2類5維元線性碼的重量譜[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2012,42(5):237-245.
WANG L J, CHEN W D. The weight hierarchies of-ary linear codes of dimension 5 in class V2[J]. Mathematics in Practice and Theory, 2012, 42(5):237-245.
[27] HU G X, ZHANG H G, WANG L J, et al. A class of the Hamming weight hierarchy of linear codes with dimension 5[J]. Tsinghua Science and Technology, 2014, 19(5):442-451.
VI-2 class of Hamming weight of-ary linear codes with dimension 5
HU Guo-xiang1,2, ZHANG Huan-guo1
(1. School of Computer, Wuhan University, Wuhan 430072, China; 2. School of Mathematics and Statistics, South-Central University for Nationalities, Wuhan 430074, China)
The Hamming weight hierarchy of a linearcodeoveris the sequence, whereis the smallest support weight of an-dimensional subcode of. According to some new necessary conditions, the VI class Hamming weight hierarchies of-ary linear codes of dimension 5 can be divided into six subclasses. By using the finite projective geometry method, VI-2 subclass and determine were researched almost all weight hierarchies of the VI-2 subclass of weight hierarchies of-ary linear codes with dimension 5.
Hamming weight, linear codes, difference sequence, projective geometry
TN 911.2
A
10.11959/j.issn.1000-436x.2016035
2015-02-02;
2015-04-20
國家自然科學(xué)基金資助項(xiàng)目(No.61303212, No.61170080, No.61332019, No.U1135004);湖北省自然科學(xué)基金資助項(xiàng)目(No.2014CBF440)
The National Natural Science Foundation of China (No.61303212, No.61170080, No.61332019, No.U1135004),The Natural Science Foundation of Hubei Province (No.2014CBF440)
胡國香(1978-),女,山東煙臺(tái)人,武漢大學(xué)博士生,中南民族大學(xué)副教授,主要研究方向?yàn)槊艽a學(xué)與信息全安全。
張煥國(1945-),男,河北元氏人,武漢大學(xué)教授、博士生導(dǎo)師,主要研究方向?yàn)樾畔踩⒖尚庞?jì)算、容錯(cuò)計(jì)算與計(jì)算機(jī)應(yīng)用等。