VI-2類(lèi)5維q元線性碼的漢明重量譜的確定

胡國(guó)香，張煥國(guó)

?

VI-2類(lèi)5維元線性碼的漢明重量譜的確定

胡國(guó)香1,2，張煥國(guó)1

（1. 武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430072；2. 中南民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北武漢 430074）

上線性碼的漢明重量譜為序列，其中，d是的維子碼的最小支撐重量。第VI類(lèi)5維元線性碼的漢明重量譜，按照新的必要條件可以分成6個(gè)子類(lèi)。運(yùn)用有限射影幾何方法研究VI-2類(lèi)的5維元線性碼的漢明重量譜，確定VI-2類(lèi)5維元線性碼的幾乎所有漢明重量譜。

漢明重量；線性碼；差序列；射影幾何

1 引言

通信系統(tǒng)中信息的傳遞離不開(kāi)編碼，而漢明重量是編碼理論中非常重要的基本概念，與編碼中碼的檢錯(cuò)以及糾錯(cuò)能力息息相關(guān)。編碼理論的創(chuàng)始人之一漢明（Hamming）提出了漢明重量。廣義漢明重量最初是由用于第2類(lèi)竊密信道的線性編碼方案所觸動(dòng)而提出的。假設(shè)發(fā)送者有bit信息被編成bit碼后通過(guò)此信道傳送給接收者。入侵者能夠從信道碼中隨意竊取到其中的bit數(shù)據(jù)。傳送的信道假設(shè)是無(wú)噪的，因而正確譯碼沒(méi)有問(wèn)題。問(wèn)題的焦點(diǎn)是如何阻止入侵者獲太多的信息，也就是設(shè)計(jì)出一種編碼方案，使入侵者截取bit數(shù)據(jù)時(shí)，對(duì)于數(shù)據(jù)的可疑度(不確定度)盡可能得大。事實(shí)上，當(dāng)一種線性碼用于上述信道時(shí)，廣義漢明重量可以完全表現(xiàn)出該碼的特性。線性碼的廣義漢明重量譜是Wei[1]首次正式提出的，廣義漢明重量是碼的最小距離的推廣。線性碼是編碼理論中一類(lèi)非常重要的碼，很多其他形式的碼都可以和線性碼找到一定的聯(lián)系。漢明重量的另一種形式被Forney稱(chēng)作長(zhǎng)度/維數(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)成的集合稱(chēng)為的支撐集，記為，即，支撐集的大小記為。

“如何確定線性碼的漢明重量譜”一直是編碼理論研究的核心問(wèn)題。關(guān)于漢明重量譜的研究，第1個(gè)研究方向是關(guān)于具體的各類(lèi)線性糾錯(cuò)碼的。由于確定是編碼理論中尚未完全解決的難題，因此的確定更加困難，目前僅有少數(shù)的幾類(lèi)碼確定了重量譜。文獻(xiàn)[12]確定了RM碼、漢明碼及其補(bǔ)碼、擴(kuò)展?jié)h明碼、極大距離可分碼等的重量譜；文獻(xiàn)[13~15]對(duì)廣義漢明重量的上下限進(jìn)行了研究；文獻(xiàn)[16,17]中，重量譜的類(lèi)別被擴(kuò)展到線性等重碼。第2個(gè)方向是關(guān)于一般線性碼的。對(duì)于一般線性碼的重量譜，傳統(tǒng)的研究方法有組合方法與計(jì)算機(jī)搜索。但是隨著線性碼維數(shù)的增加，重量譜的類(lèi)別也呈指數(shù)增加，對(duì)于高維數(shù)線性碼重量譜的研究更加困難，這2種方法均不太適用。目前來(lái)看，有限射影幾何方法對(duì)于高維數(shù)線性碼重量譜的研究較為適用。

1.2 相關(guān)工作

1992年，密碼學(xué)家Helleseth[18]提出了確定一般線性碼的所有可能的漢明重量譜，這也是編碼理論中一個(gè)非常有意義的理論問(wèn)題。1996年，陳文德等[19]提出了有限射影幾何方法，并第一次有效地用于確定4維元線性碼的漢明重量譜。他們還把4維元線性碼及其漢明重量譜分成了9類(lèi)，用有限射影幾何方法取得了豐富的分類(lèi)研究成果，參見(jiàn)文獻(xiàn)[20,21]等。文獻(xiàn)[22]對(duì)4維元線性碼的漢明重量譜進(jìn)行研究，確定4維元線性碼的幾乎所有的漢明重量譜。文獻(xiàn)[23]中把5維元線性碼及其漢明重量譜分成6類(lèi)，并對(duì)6類(lèi)碼中的II-1類(lèi)進(jìn)行了研究；文獻(xiàn)[24]對(duì)II-2類(lèi)進(jìn)行了研究。文獻(xiàn)[25]確定了5維元線性碼V-1類(lèi)的幾乎所有的漢明重量譜。文獻(xiàn)[26]確定了5維元線性碼V-2類(lèi)的幾乎所有的漢明重量譜。在文獻(xiàn)[27]中第VI類(lèi)5維元線性碼的漢明重量譜又被分成了6個(gè)子類(lèi)，并對(duì)其中的VI-1類(lèi)進(jìn)行研究，確定該類(lèi)的幾乎所有的漢明重量譜。本文將對(duì)文獻(xiàn)[27]中的VI-2子類(lèi)進(jìn)行研究，并確定其幾乎所有的漢明重量譜。

本文主要研究了文獻(xiàn)[27]中5維元線性碼的第VI-2類(lèi)的漢明重量譜。利用有限射影幾何方法，通過(guò)往4維空間進(jìn)行投影，把重量譜的確定轉(zhuǎn)化為4維空間中的點(diǎn)、線、面、體的賦值函數(shù)的確定問(wèn)題，使確定重量譜這一抽象的理論問(wèn)題變得更為形象化。

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

(1)

3 主要結(jié)果

文獻(xiàn)[27]中把5維元線性碼的第VI類(lèi)的差序列的必要條件分成6個(gè)子類(lèi)，并對(duì)其中的VI-1類(lèi)進(jìn)行了研究，其他5個(gè)子類(lèi)的重量譜均未確定。相比VI-1類(lèi)來(lái)說(shuō)，VI-2重量譜的確定更為困難，因?yàn)楫?dāng)取得上界時(shí)，賦值函數(shù)的取值不完全為的整數(shù)倍，需要考慮將進(jìn)行分?jǐn)?shù)化處理。

本文研究這6類(lèi)中的VI-2個(gè)子類(lèi)。由文獻(xiàn)[27]可得VI-2類(lèi)差序列的必要條件如下。

下面將構(gòu)造出VI-2類(lèi)的幾乎所有可能的漢明重量譜，即證明上述必要條件是幾乎充分的，以下的引理1～引理4將給出各種條件下的詳細(xì)證明與賦值函數(shù)的構(gòu)造。

引理1 設(shè)

(3)

(4)

證明 把式(2)～式(5)代入后，得

定義下面這些符號(hào)為

點(diǎn)、線、面、體之間的關(guān)系說(shuō)明如下。

證明 定義以下一些符號(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類(lèi)的幾乎所有的差序列。

4 結(jié)束語(yǔ)

本文對(duì)5維元線性碼中的第VI-2類(lèi)進(jìn)行研究，運(yùn)用有限射影幾何方法通過(guò)對(duì)射影空間中的點(diǎn)進(jìn)行賦值，得到不同條件下賦值函數(shù)的構(gòu)造，從而得到第VI-2類(lèi)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ù)/長(zhǎng)度輪廓及其應(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維元線性碼重量譜的分類(lèi)與確定[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類(lèi)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] 王麗君，陳文德.一類(lèi)5維元線性碼重量譜的確定[J].科學(xué)通報(bào)，2011,56(25):2150-2155.

WANG L J, CHEN W D.

[26] 王麗君，陳文德. V2類(lèi)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

國(guó)家自然科學(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)

胡國(guó)香（1978-），女，山東煙臺(tái)人，武漢大學(xué)博士生，中南民族大學(xué)副教授，主要研究方向?yàn)槊艽a學(xué)與信息全安全。

張煥國(guó)（1945-），男，河北元氏人，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩⒖尚庞?jì)算、容錯(cuò)計(jì)算與計(jì)算機(jī)應(yīng)用等。