VI-2類5維q元線性碼的漢明重量譜的確定

胡國香，張煥國

?

VI-2類5維元線性碼的漢明重量譜的確定

胡國香1,2，張煥國1

（1. 武漢大學計算機學院，湖北武漢 430072；2. 中南民族大學數學與統計學學院，湖北武漢 430074）

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

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

1 引言

通信系統中信息的傳遞離不開編碼，而漢明重量是編碼理論中非常重要的基本概念，與編碼中碼的檢錯以及糾錯能力息息相關。編碼理論的創始人之一漢明（Hamming）提出了漢明重量。廣義漢明重量最初是由用于第2類竊密信道的線性編碼方案所觸動而提出的。假設發送者有bit信息被編成bit碼后通過此信道傳送給接收者。入侵者能夠從信道碼中隨意竊取到其中的bit數據。傳送的信道假設是無噪的，因而正確譯碼沒有問題。問題的焦點是如何阻止入侵者獲太多的信息，也就是設計出一種編碼方案，使入侵者截取bit數據時，對于數據的可疑度(不確定度)盡可能得大。事實上，當一種線性碼用于上述信道時，廣義漢明重量可以完全表現出該碼的特性。線性碼的廣義漢明重量譜是Wei[1]首次正式提出的，廣義漢明重量是碼的最小距離的推廣。線性碼是編碼理論中一類非常重要的碼，很多其他形式的碼都可以和線性碼找到一定的聯系。漢明重量的另一種形式被Forney稱作長度/維數輪廓，在線性碼的格子復雜度分析[2~6]、譯碼分析[7~9]、檢錯分析[10]等方面都有非常重要的應用，文獻[11]也詳細討論了其應用。重量譜的概念由Wei提出以后，立即成為編碼理論的一個前沿研究熱點。

1.1 基礎知識

對于一個碼，中的所有碼字的非零位置的全體所構成的集合稱為的支撐集，記為，即，支撐集的大小記為。

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

1.2 相關工作

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

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

2 預備知識

(1)

3 主要結果

文獻[27]中把5維元線性碼的第VI類的差序列的必要條件分成6個子類，并對其中的VI-1類進行了研究，其他5個子類的重量譜均未確定。相比VI-1類來說，VI-2重量譜的確定更為困難，因為當取得上界時，賦值函數的取值不完全為的整數倍，需要考慮將進行分數化處理。

本文研究這6類中的VI-2個子類。由文獻[27]可得VI-2類差序列的必要條件如下。

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

引理1 設

(3)

(4)

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

定義下面這些符號為

點、線、面、體之間的關系說明如下。

證明 定義以下一些符號（如圖2所示）。

所以可令

證明 先定義以下一些符號（如圖3所示）。

1) 由點的非負性，可得

又由

又由

又由

又由

3）由面之間的關系可得

又由

1) 由點的非負性，可得

又由

3) 由面之間的關系，可得

又由

所以，

由上述引理1～引理4，可得如下的定理。

所以，由引理1～引理4，該定理的充分性得證，也就得到了VI-2類的幾乎所有的差序列。

4 結束語

本文對5維元線性碼中的第VI-2類進行研究，運用有限射影幾何方法通過對射影空間中的點進行賦值，得到不同條件下賦值函數的構造，從而得到第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重量,維數/長度輪廓及其應用[J].電子學報,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] 羅守山,陳萍,楊義先.廣義漢明重量下限函數L()的新證明[J].北京郵電大學學報,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] 羅守山,楊義先,吳偉陵.線性碼廣義漢明重量的上限函數[J].通信學報, 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重量上/下界的對偶定理[J].通信學報,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] 岳殿武,胡正名.關于BCH碼的廣義Hamming重量上下限[J].通信學報,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].電子科學學刊, 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] 岳殿武,江凌云,段冰娟.線性等重碼格子復雜度的確定[J].應用科學學報,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].系統科學與數學，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].數學的實踐與認識, 2011, 41(21): 244-252.

WANG L J, CHEN W D.MathematicsinPracticeandTheory, 2011, 41(21):244-252.

[25] 王麗君，陳文德.一類5維元線性碼重量譜的確定[J].科學通報，2011,56(25):2150-2155.

WANG L J, CHEN W D.

[26] 王麗君，陳文德. V2類5維元線性碼的重量譜[J].數學的實踐與認識，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

國家自然科學基金資助項目（No.61303212, No.61170080, No.61332019, No.U1135004）；湖北省自然科學基金資助項目（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-），女，山東煙臺人，武漢大學博士生，中南民族大學副教授，主要研究方向為密碼學與信息全安全。

張煥國（1945-），男，河北元氏人，武漢大學教授、博士生導師，主要研究方向為信息安全、可信計算、容錯計算與計算機應用等。