最優少重量二元碼的構造

任 磊，廖群英

（四川師范大學 數學科學學院，四川 成都 610066）

其中Ai（1≤i≤n）為碼中漢明重量為i的碼字個數.序列（1，A1，A2，…，An）為碼的重量分布.若序列（A1，A2，…，An）中非零Ai（1≤i≤n）的個數為t，則稱碼為t權重二元碼.

設p為素數，q ＝pn，q是q 元有限域，qk為有限域q的k 次有限擴張.令D ＝｛d1，d2，…，dn｝?qk，記Tr（x）＝x +xq+… +xqk-1為有限域qk到q上的跡映射，則可得到q上碼長為n 的線性碼

Ding 等［1-2］第一次給出利用定義集構造線性碼的一般方法，隨后眾多學者通過選取合適的定義集構造了許多碼［3-6］，并且這些碼能夠應用于密鑰共享方案［7］和身份認證［8］.

設R是有限交換環，Rm是環R的m（m≥2）次擴張，是Rm的乘法群.定義

上的跡碼為

其中Tr（·）是Rm到R的一個R-線性函數.基于上述構造方法，學者們給出許多定義在環上的少重量線性碼［9-17］.

設m（m≥2）是正整數，向量v ＝（v1，v2，…，vm）∈的支撐集定義為

則向量v的漢明重量為wt（v）＝|Supp（v）|.2［m］為［m］＝｛1，2，…，m｝的冪集.定義到2［m］的一個映射如下：

且|A／B|表示集合A／B中元素的個數.

對于參數為［n，k，d］2的一個二元碼，若參數滿足Griesmer界，即

2019 年，Hyun等［17-18］利用簡單復合體構造了最優二元有限族和極小線性碼；隨后，2020 年，Wu等［19］運用簡單復合體，構造了環2+u2上2 類少重量線性碼.基于他們的工作，本文在有限域2上利用簡單復合體構造了2 類最優少重量二元碼，給出了2 類碼的重量分布，并證明了它們的參數都滿足Griesmer界.

1 預備知識

其中u ＝（u1，u2，…，um），且Z是整數環.

為計算碼的重量分布，先給出如下引理.

引理1.1［17］設Δ?是中的一個簡單

復合體，則

在本文中，2 個簡單復合體

設a ＝（α，β），l ＝（t1，t2），其中α ＝（α1，α2，…，αm），β ＝（β1，β2，…，βm）∈，t1∈ΔA，t2∈.若a ＝0，則ωH（ca）＝0.因此，不妨設a≠0，此時由L1的定義可得

定理2.1設A，B?［m］且0 ＜|B| ＜m.若ΔA、ΔB是m2的2 個簡單復合體，，則碼L1的碼長為2|A|（2m-2|B|），碼字個數為2m+|A|，且重量分布如表1 所示.

表1 碼L 1的重量分布Tab.1 Weight distribution of code L 1

表1 碼L 1的重量分布Tab.1 Weight distribution of code L 1

再由（1）式可得

其中δ是符號函數.

設X ＝Supp（α），Y ＝Supp（β），下面分2 種情形討論.

情形1若β ≠0，此時由（2）式可得

1）若χ（α|A）χ（β|B）＝1，則

又由χ（α|A）χ（β|B）＝1，可知X∩A ＝Y∩B ＝?.而Y≠?，故X∩A ＝?，Y∩B ＝?，Y≠?.記

故碼字個數為|T0| ＝2m-|A|（2m-|B|-1）.

2）若χ（α|A）χ（β|B）＝0，則

又χ（α|A）χ（β|B）＝0，故X∩A≠?或Y∩A≠?且Y≠?.記

從而T1∪T2∪T3＝2［m］×2［m］.又

從而|T1| ＝22m-|T2| -|T3|，故碼字個數為

情形2若β ＝0，此時由（2）式可得

1）若χ（α|A）＝1，則ωH（ca）＝0.又χ（α|A）＝1，故X∩A ＝?.再由Y ＝?以及X，Y≠?，可知X≠?.記

故碼字個數為|T1| ＝2m-|A|-1.

2）若χ（α|A）＝0，則

又χ（α|A）＝0，故X∩A≠?，從而X∩A≠?，Y ＝?.記T0＝｛（X，Y）|X∩A≠?，Y ＝?｝，故碼字個數為2m-2m-|A|.

定理2.2碼L1是最優二元碼.

證明由定理2.1 可知，碼L1的參數為［2|A|（2m-2|B|），m+|A|，2|A|-1（2m-2|B|）］2，故

2.2 碼L2的重量分布設a ＝（α，β），l ＝（t1，t2），其中α ＝（α1，α2，…，αm），β ＝（β1，β2，…，βm）∈，t1∈，t2∈.若a ＝0，則ωH（ca）＝0.因此，不妨設a≠0，此時由L2的定義可得

定理2.3設A，B?［m］且0 ＜|A|，|B| ＜m.若ΔA、ΔB是的2 個簡單復合體，，則碼L2的碼長為（2m-2|A|）（2m-2|B|），碼字個數為22m，且重量分布如表2 所示.

表2 碼L 2的重量分布Tab.2 Weight distribution of code L 2

表2 碼L 2的重量分布Tab.2 Weight distribution of code L 2

證明由定義容易知道碼L2的碼長為|L2| ＝（2m-2|A|）（2m-2|B|）.設0≠a ＝（α，β），其中α ＝（α1，α2，…，αm），β ＝（β1，β2，…，βm）∈.由（3）式可得

設X ＝Supp（α），Y ＝Supp（β），下面分4 種情形討論.

情形1若α ＝0且β ≠0，則由（4）式可得［| L2| +（2m-2|A|）2|B|χ（β| B）］.

1）若χ（β|B）＝1，則

由χ（β| B）＝1，可知Y ∩B ＝?.又α ＝0，β ≠0，故X ＝?，Y ≠?，從而Y ∩B ＝?，Y ≠?且X ＝?.若記

T1＝｛（X，Y）| Y ∩B ＝?，Y ≠?，X ＝?｝，故碼字個數為|T1| ＝2m-|B|-1.

2）若χ（β|B）＝0，則

由χ（β| B）＝0，可知Y ∩B ≠?.又α ＝0，β ≠0，故X ＝?，Y ≠?，從而Y ∩B ≠?且X ＝?.若記

故碼字個數為|T0| ＝2m-2m-|B|.

情形2若α ≠0且β ＝0，則由（4）式可得

1）若χ（α|A）＝1，則

由χ（α|A）＝1，可知X∩A ＝?.又α≠0，β ＝0，故X≠?，Y ＝?，從而X∩A ＝?，X≠?且Y ＝?.若記

T1＝｛（X，Y）| X ∩A ＝?，X ≠?，Y ＝?｝，故碼字個數為|T1| ＝2m-|A|-1.

2）若χ（α|A）＝0，則

由χ（α|A）＝0，可知X∩A≠?.又α≠0，β ＝0，故X≠?，Y ＝?，從而X∩A≠?且Y ＝?.若記

故碼字個數為|T0| ＝2m-2m-|A|.

情形3若α ＝β≠0，則由（4）式可得

1）若χ（α|A）χ（β|B）＝1，則

由χ（α|A）χ（β|B）＝1，可知X∩A ＝?，Y∩B ＝?.又α ＝β≠0，故X ＝Y≠?，從而X∩（A∪B）＝?且X≠?.若記

故碼字個數為|T1| ＝2m-|A∪B|-1.

2）若χ（α|A）χ（β|B）＝0，則

由χ（α|A）χ（β|B）＝0，可知X∩A≠?，Y∩B≠?.又α ＝β≠0，故X ＝Y≠?，從而X∩（A∪B）≠?且X≠?.若記

故碼字個數為|T0| ＝2m-2m-|A∪B|.

情形4若α ≠β，α ≠0，β ≠0，則由（4）式得

1）若χ（α|A）χ（β|B）＝1，則

由χ（α| A）χ（β| B）＝1，知X ∩A ＝Y ∩B ＝?.又α ≠β，α ≠0，β ≠0故X ≠Y，X ≠?且Y ≠?.令

則由T2＝T1∪T0及| T2| ＝| T1|+| T0|，可得|T0| ＝|T2| -|T1|.故碼字個數為

2）若χ（α|A）χ（β|B）＝0，則

由χ（α|A）χ（β|B）＝0，可知χ（α|A）＝0，χ（β|B）＝1或χ（α|A）＝1，χ（β|B）＝0或χ（α|A）＝0，χ（β|B）＝0.

當χ（α| A）＝1，χ（β| B）＝0時，可得X ∩A ＝?，Y ∩B ≠?.又α ≠β，α ≠0，β ≠0，故X ≠Y，X ≠?，Y ≠?.令

則由T2＝T0∪T1及|T2| ＝|T0|+|T1|，可知|T0| ＝|T2| -|T1|.又|T2| ＝（2m-|A|-1）（2m-2|B|），|T1| ＝2m-|A|（2|B／A|-1），從而

當χ（α| A）＝0，χ（β | B）＝1 時，易得X ∩A ≠?，Y ∩B ＝?.又α ≠β，α ≠0，β ≠0，故X ≠Y，X ≠?，Y ≠?.令

當χ（α| A）＝0，χ（β | B）＝0 時，可得X ∩A ≠?，Y ∩B ≠?.又α ≠β，α ≠0，β ≠0可知X ≠Y，X ≠?，Y ≠?.令

故當χ（α| A）χ（β | B）＝0 時，可得碼字個數為|T0|+||+||，即

根據上述證明可知，當A ＝B時，有如下推論.

推論2.4若A ＝B，則碼L2是3 權重碼，其重量分布如表3 所示.

表3 碼L 2（A ＝B）的重量分布Tab.3 Weight distribution of the code L 2 with A ＝B

表3 碼L 2（A ＝B）的重量分布Tab.3 Weight distribution of the code L 2 with A ＝B

定理2.5若A ＝B且|A| ＝m-1，則碼L2為最優二元碼.

證明由定理2.3 可知，若A ＝B，|A| ＝m-1，則碼L2的參數為［22m-2，2m-1，22m-3］2，從而有

3 應用舉例

下面給出2 個具體例子.

例3.1取m ＝3，ΔA＝｛（0，0，0），（0，0，1）｝，ΔB＝｛（0，0，0），（0，1，0）｝，則

進而，由定義可得

另一方面，由m ＝3，|A| ＝|B| ＝1，以及定理2.1，可知碼L1的碼長為12、碼字個數為16，以及重量分布如表4 所示，故可得碼L1的參數為［12，4，6］2，以及重量計數器為

表4 碼L 1（|A| ＝|B| ＝1）的重量分布Tab.4 Weight distribution of the code L 1 with |A| ＝|B| ＝1

表4 碼L 1（|A| ＝|B| ＝1）的重量分布Tab.4 Weight distribution of the code L 1 with |A| ＝|B| ＝1

容易驗證其參數［24，5，12］2滿足Griesmer 界，故L1為最優二元碼.

表5 碼L 1的重量分布Tab.5 Weight distribution of the code L 1

表5 碼L 1的重量分布Tab.5 Weight distribution of the code L 1

表6 碼L 1的重量分布Tab.6 Weight distribution of the code L 1

表6 碼L 1的重量分布Tab.6 Weight distribution of the code L 1

例3.2取m ＝3，A ＝B且|A| ＝2.按照例3.1的方法，則可得碼L2的全體碼字，從而可以直接計算出碼的參數為［16，5，8］2，以及重量計數器為

容易驗證其參數［16，5，8］2滿足Griesmer 界，故L2為最優二元碼.

碼字個數為22m，且重量分布如表7 所示.

表7 碼L 2的重量分布Tab.7 Weight distribution of the code L 2

表7 碼L 2的重量分布Tab.7 Weight distribution of the code L 2

碼字個數為22m，且重量分布如表8 所示.

表8 碼L 2的重量分布Tab.8 Weight distribution of the code L 2

表8 碼L 2的重量分布Tab.8 Weight distribution of the code L 2