数理解析研究所講究録 1420 巻 2005 年 150-162

150
Some Results on the Local Weight Distribution of
Binary Linear Codes
大阪大学・大学院情報科学研究科藤原融 (Toru Fujiwara)
Graduate School of Information Science and Technology
Osaka University
大阪大学・大学院情報科学研究科安永憲司 (Kenji Yasunaga)
Graduate School of Information Science and Technology
Osaka University

1

Introduction

In a binary linear code, a zero neighbor is a cod eword whose Voronoi region shares afacet with that of the all-zero codeword [2]. The local weight distribution $[1, 12]$ (or local
distance profile [2, 3, 4, 5, 11] of a binary linear code is defined as the weight distributionof zero neighbors in the code. Knowledge of the local weight distribution of a code isvaluable for the error peiforman ce analysis of the code. For example, tl le local weight
distribution gives a tighter upper bound on error .
for soft decision decoding
over AWGN channel than the usual union bound [5].
Formulas for local weight distribution are only known for certain classes of codes,
Hamming codes and second-order Reed-Muller codes. Although an efficient method to
ex amine zero neighborship of codeword is presented in [2], the mputation
obtaining
the local weight distribution is a very time-consuming task. As Agrell noted in [2], theauto morphism group of the code can help reduce the complexity. Using the group of
cyclic permutations, Mohri et al. devised a computation algorithm for cyclic codes. We
call the algorithm the MHM algorithm in this resume. By using the algorithm, theyobtained the local weight distributions of the $(63, k)$ binary primitive BCH codes with
$k\leq 45[3,4]$ . They also obtained the distirubutions for A $=51,57$ by their anotheralgorithm [3]. The MHM algorithm reduces the computational complexity by using thefollowing invariance property [2]: Any cyclic permutation of a codeword is a zero neighbor
if and only if the codeword is a zero neighbor. It generates the representative codeword
and the number of the equivalent codewords, which are able to be cyclic-permuted into
the representative one, and checks whether each of the representatives is a zero neighboror not. The key subalgorithm in the algorithm is the generation of the representative$)$$\mathrm{P}^{1\mathrm{o}\mathrm{b}\mathrm{a}\mathrm{b}\mathrm{i}1\mathrm{i}\mathrm{t}\mathrm{y}}$$\mathrm{f}\mathrm{o}1$$\mathrm{c}\mathrm{o}$codewords.
The MHM I algorithm can also be applied straightforwardly to compute the local
weight distribution of extended cyclic codes (see Corollary 2). Extended primitive BCH
codes are closed under the affine group of permutations, which is larger than tl cydic
group of permutations. The invariance property for the cyclic permutations can be$\iota \mathrm{e}$151generalized to that for any group of permutations [2]. Using the invariance property
for the larger group of permutations, we lnay reduce the number of the representativecodewords. However, it is not easy to obtain the representative codewords and thenumber of the equivalent codewords.
In this resume, we give some of our results on the local weight distributions, presented
in [11, 12, 13, 14]. Frist, we give an algorithm for computing the local weight distributionof binary linear codes which are closed under any group of permutations. To use theinvariance property, we will apply the invariance property to the set of cosets of a subcode
rather than the set of codewords. The representative cosets and the number of equivalentcosets are computed in the proposed algorithm. This reduces the complexity of finding
the representatives, which is much smaller than that for checking the zero neighborshipfor every representative codewords. This idea was introduced in [7] for computing theweight distributions of extended binary primitive BCH codes, We show that the idea canalso be applied for the local weight distribution, To reduce the complexity more, we use
the trellis structure of the code, in checking the zero neighborship.
We apply the proposed algorithm to extended binary primitive BCH codes andextended binary primitive BCH code
obtain the local weight distributions of thefor $\leq 50[11],[12]$ . The complexity of the proposed algorithm is about 1/64 as muchfor the codes of length 128. Furthermore, we obtain theas that of the MHM
local weight distributions of the third-order Reed-Muller code of length 128.
However, for cyclic codes, the complexity is not reduced. Then, the local weight
were not obtained although
distributions of the $(127, k)$ primitive BCH codes for A
extended primitive BCH codes are obtaiend for $k\leq 50$ .
those of the corresponding
A method for obtaining the local weight distribution of a code from that of its extended
code should be considered.
For this purpose, relations between local weight distributions of a binary linear codeand its extended code are derived. A concrete relation is presented for the case that theextended code is transitive invariant and contains only codewords with weight multipleof four. Extended binary prim itive BCH codes and Reed-Muller codes are transitive$(12\mathrm{S}, k)$$k$$\mathrm{a}1\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}^{-}1$$\geq 36$$(12\mathrm{S}, k)$invariant codes.
A relation between local weight distributions of a binary linear code and its evenweight subcode is also given. By using the relations, the local weight distributions of
the $(127, k)$ binary primitive BCH codes for $36\leq k\leq 50$ , the punctured third-order
Reed-Muller code of length 127, and their even weight subcodes are obtained from theprimitive BCH codes for $36\leq k\leq 50$ and the
local weight distributions of tl lethird-order Reed-Muller code of length 128.
$(12\mathrm{S}, k)$152
2

Local Weight Distribution

Let be a binary $(n, k)$ linear code. Define a mapping from {0, 1} toand $s(1)=1$ . The mapping is naturally extended to one fromneighbor is defined as follows:$C$$\mathrm{R}$$\mathrm{s}$$\{0, 1\}^{n}$$s$

Definition 1 (Zero neighbor) For
where $0=(0, 0, \ldots, 0)$ . The codeword

$v$

$v$

as $s(0)=-1$
to. Zero$\mathrm{R}^{n}$

as $m_{0}= \frac{1}{2}(s(0)+s(v))$ ,, define
is a zero neighbor iff$\in C$$m_{0}\in \mathrm{R}^{n}$$d_{E}(m_{0}, s(v))=d_{E}(m_{0}, s(0))<d_{E}(m_{0}, s(v’))$for any$v’\in C\backslash \{0, v\}$

where $d_{E}(x, y)$ is the squared Euclidean distance be rween

$x$

,
(1)

,

and

$\prime y$in$\mathrm{R}^{n}$.

The local weight distribution is defined as follows:
Definition 2 (Local weight distribution) Let
be the number of zero neighborswith weightin C. The local weight distribution ofis defined as the $(n+1)$ -tuple$L_{w}$$C$$w$$(L_{0}, L_{1}, \ldots, L_{n})$.

The following lemma is useful to check whether a given codeword is a zero neighbor ornot.

Lemma 1[2] $v\in C$ is a zero neighbor if and only if there does not exist
such that Supp(v’) Supp(v) . Note that Supp(v) is the set of support of , which is theset of positions of nonzero elements in.
$v’\in C\backslash \{0\}$$v$$\subset<$

$v$

$=$

$(v_{1}, v_{2}, .

, .

, v_{n})$

Let $A_{w}(C)$ be the number of codewords with weight in . For the local weight
distribution and the (global) weight distribution $(A_{0}(C), A_{1}(C)$ ,, $A_{n}(C))$ , we havethe following lemma $[1, 6]$ .
$w$

$C$

$\ldots$

Lemma 2 Let d be the minimum distance of C. Then, we have thai$L_{w}(C)=\{$$A_{w}(C)_{7}$$w<2d$ ,0,$w>n$ $-k+1$ .

(2)

When the weight distribution is known, only $L_{w}(C)$ with $2d\leq w\leq n-k+1$ need to becomputed to obtain the local weight distribution. Generally, the complexity for computing the local weight distribution is larger than that for computing the weight distribution.
Therefore, Lemma 2 is useful for obtaining local weight distributions. Moreover, when
all the weights in a code is confined in $w<2d$ and $w>n-k+1$ , the local weight distributhon can be obtained from the weight distribution straightforwardly. For example,
the local weight distribution of the $(n, k)$ primitive BCH code of length 63 for, of$k\leq29$
length 127 for, and of length 255 for $k\leq 45$ can be obtained from their weight$w$$k\leq 1\mathrm{S}$distributions.
The MHM algorithm proposed in [4] uses the following invariance property undercyclic permutations, as well as Lemma 1,

153
Theorem 1 [4] Let C be a binary cyclic code. Any cyclic permuted codeword of v iszero neighbor if a codeword v $\in C$ is a zero neighbor.

$a$be an times cyclic permuted
be a binary cyclic cole, andCorollary 1 Let
is thewhere
codeword of $v\in C$ . Consider a set. Then, (1) if is a zero neighbor,period of , which is the minimum such that
all codewords in the set are zero neighbors; and (2) otherwise, all codewords in are
not zero neighbors.
$\sigma^{i}v$$C$$\mathrm{S}$$i$$p(\sigma, v)$$=\{v, \sigma v, \sigma^{2}v, \ldots, \sigma^{p(\sigma,v)-1}v\}_{f}$$\sigma^{i}v=v$$\mathrm{i}$$\sigma$

$v$

$S$

$S$

In the MHM algorithm, all codewords are partitioned into the sets described in
Corollary 1. Only one representative codeword in each sets is generated and checked
whether it is a zero neighbor or not.
We can easily modify the MHM algorithm to compute the local weight distributionof the extended cyclic code using the following corollary:
Corollary 2 Let
For $v\in C_{f}$ let

$C$

$v’$

of

$C_{\mathrm{e}\mathrm{x}}$$C_{\mathrm{e}\mathrm{x}}$$\mathrm{e}\mathrm{x}(v)$codeword

be a binary cyclic code and its extended code, respectively.
and. Then, for any cyclic perm utel
be the corresponding codeword in.
is a zero neighbor in
is a zero neighbor in
if$C_{\mathrm{e}\mathrm{x}}$$v_{;}\mathrm{e}\mathrm{x}(v’)$$C_{\mathrm{e}\mathrm{x}}$$\mathrm{e}\mathrm{x}(v)$As mentioned in Section 1 the extended primitive BCH codes are closed larger class of
permutations, and Theorem 1 can be generalized to any group of permutations of theautomorphism group of the code [2]. In the following section, we review the invarianceproperty under a group of permutation, and present a coset partitioning technique to use
the property effectively.

3

Coset Partitioning for Computing the Local Weight
Distribution of Codes Closed under a Group of

Permutations
3,1

An invariance property under permutations

For a permutation$\pi$

and a set of vectors$D$, the set of the permuted vectors $\pi[D]$ isdefined as$\pi[D]=\{\pi v :v \in D\}$

(3)

.

is
The automorphism group of a code $C$ is the set of all permutations by which.
,,
permuted into , and denoted by
An invariance property under the automorphism group is given in the following
$C$

$C$

$\mathrm{A}\mathrm{u}\mathrm{t}(C)$$\mathrm{i}.\mathrm{e}.$$\mathrm{A}\mathrm{u}\mathrm{t}(C)=\{\pi :\pi[C]=C\}$

theorem.

Theorem 2 For$\pi\in \mathrm{A}\mathrm{u}\mathrm{t}(C)$and v$\in C_{f}\pi v$

is a zero neighbor if v is a zero neighbor.

154This theorem extends Corollary 1 as follows:

Corollary 3 For $v\in C$ , consider a set $S=$ {wv :}. Then, (1) if
zero neighbor, all codewords in are zero neighbors; and (2) otherwise, all codewords inare not zero neighbors.
$\forall\pi\in \mathrm{A}n\mathrm{t}(C)$$v\iota s$

$a$

$S$

$S$

It is not easy to devise a similar algorithm as the MHM algorithm, since for almost
all group of permutations, no efficient way is known for generating the representativecod ewords and obtaining the number of the equivalent codewords. To use this invarianceproperty, we apply the invariance property to the set of cosets of a subcode rather than
the set of codewords.

3.2

Local weight subdistribution for a coset

For a binary ( , Ax) linear code
denoteset of cosets of $C’$ in$n$$\mathrm{t}1_{1}\mathrm{e}$$|C/C’|=2^{h-k’}\}$

and

$C$
$C$

and its linear subcode with dimension , iet $C/C’$, that is, $C/C’=\{v+C’ : v\in C\}$ . Then,$f_{\hat{v}}’$$C=\cup D\in C/C$

’D.

(4)

Definition 3 (Local weight subdistribution for a coset) The local weight subdistribution for a coset $D\in C/C’$ is the weight $dis$ tribution of zero neighbors of in $D$ .
, $|LS_{n}(D)|)f$ where
The local weight subdistribution for $D$ is $(|LS_{0}(D)|)|LS_{1}(D)|$ ,$C$$\ldots$$LS_{w}(D)$$=${ $v\in D$ : Supp$(\mathrm{v}^{\mathit{1}})\not\leqq$

Supp(v) for any $v’\in C\backslash \{0, v\}$ ,and the Ha mning weight of

$v$

is

$w$

},

(5)

with $0\leq w\leq n$ .
Then, from (4), the local weight distribution of $C$ is given as the sum of the local weight
subdistributions for the cosets in $C/C’$ , that is,$L_{w}= \sum_{D\in C/c_{J}\prime}|LS_{w}(D)|$(6).

The following theorem gives an invariance property under permutations for cosets.
Theorem 3 For , $D_{2}\in C/C’$ , the local weight subdistnbution for
are the same if there exists
Aut(C) such that $\pi[D_{1}]=D_{2}$ .
$D_{1}$$D_{1}$and that for$D_{2}$$\pi\in$

3.3

Partitioning the set of cosets with the same local weight
subdistribution

We give a condition for cosets having the same local weight subdistribution. The following
lennna gives the set of all permutations by which every coset in $C/C’$ is permuted into
one in $C/C’$ .

155
Lemma 3 For a linear code C and its linear subcode $C’$ ,{yr : $\pi[D]\in C/C’$ for any $D\in C/C’$ }$=$Aut(C)$\cap$

Ant $(C’)$ .

Aut(C) Aut(C”) (or even Aut(C)) is generally not known. Only subgroups ofAut(C) Ant(C’) are known. Therefore, we use a subgroup.
$\cap$$\cap$

Definition 4 Let be a subset of Aut(C)\cap Aut(C’). For , $D_{2}\in C’/C_{J}’$ we denotesuch that $\pi[D_{1}]=D_{2}$ .
if and only if there exists$D_{1}$$\Pi$$\pi\in\Pi$$D_{1}\sim\Pi D_{2}$Lemma 4 The relation$.’\zeta\sim\Pi$”

is an equivalence relation on $C/C’$ if TI forms a group.

,
When the set of cosets are partitioned into the equivalence classes by the relation
the local weight subdistributions for cosets which belong to the same equivalence classare the same.
We give a useful theorem for partitioning the set of cosets into equivalence classes$(\zeta’)\sim\Pi$by the relation$‘\zeta\sim\Pi\cdot$”

Theorem 4 Let II be a subset of Aut(C)havefor anyif.
$D_{1}\sim\Pi D_{2}$$\pi v_{1}\in D_{2}$$\cap \mathrm{A}\mathrm{u}\mathrm{t}(C’)$$v_{1}\in D_{1}$. For$D_{1}$, $D_{2}\in C/C’$ and$\pi\in\Pi_{f}$we.

From Theorem 4, to partition the set of cosets into equivalence classes, we only
need to check whether the representative codeword of a coset is permuted into anothercoset. After partitioning into equivalence classes, the local weight subdistribution for only
one coset in each equivalence class needs to be computed. Thereby the computational.
complexity is redu$\iota \mathrm{c}\mathrm{e}\mathrm{d}$An Algorithm for Computing the Local Weight4

Distribution
4.1

Outline of the algorithm

On the basis of the method of partitioning the set of cosets described in the previous
section, we propose an algorithm to compute the local weight distribution as follows:
1. Choose a subcode$C^{l}$

and a subgroup$\Pi$of permutations of Aut(C)2. Partition $C/C’$ into equivalence classes with permutations in
number of codewords in each equivalence class.

$\Pi$$\cap \mathrm{A}\mathrm{u}\mathrm{t}(C’)$.

, and obtain the

3. Compute the local weight subdistributions for the representative cosets in each
equivalence ciass.

4. Sum up all the local weight subdistributions

158
Computational complexity

4.2

Here, we analyze computational complexity of the proposed algorithm for the binary$(n, k)$ linear code $C$ , assuming that the subcode $C’$ with dimension
is given. Also, tocheck whether a codeword is a zero neighbor or not, the procedure presented in [2] ismputational
used as in the MHM algorithm. The procedure uses Lemma 1 and its$O(n^{2}k)$.
complexity to check one codeword isSince the number of codewords in each cosets is , the total number of codewords to, where is the number of the equivalence classes. The
be checked by the procedure iscomputational complexity to check one codeword is $O(n^{2}k)$ . Hence, the time complexityof Step (3) of the proposed algorithm is $O(n^{2}k\cdot e2^{k’})$ . The time complexity of Step (2),partitioning the set of cosets, is $O(n(k-k’)2^{k-k’}|\Pi|)[11]$ .
$e2^{k’}+n(k$Therefore, the time complexity of the entire algorithm is$k’)2^{k-k’}|\Pi|)$ .
, and the complexity ofis chosen as $k’>k/2$ , thenWhenpartitioning the set of cosets is much smaller than of computing the local weight subdistributions for cosets.
The space complexity of the entire algorithm is 0 $((k-k’)2^{k-k’})[11]$ , since the space
mplexity for computing the local weight subdistributions is much smaller than that forpartitioning the set of cosets.
$k’$$\mathrm{c}\mathrm{o}$$2^{k’}$$e2^{k’}\backslash$$e$$O(n^{2}k\cdot$-$2^{k’}>2^{k-k’}\wedge$$k’$$\mathrm{c}\mathrm{o}$Selection of the subcode

4.3

We should choose the subcode to make the number of permutations in large.
If there are several subcodes with the sam, then the subcode with the smaller
dimension should be chosen to minimize the number of codewords that need to be checked,
as long as the complexity of partitioning the set of cosets is relatively small.
$\Pi$$\mathrm{l}\mathrm{e}$

4.4

$\Pi$

A method for checking the zero neighborship using the trellis structure

We consider reducing the complexity of checking whether a codeword is a zero neighboror not.
For $v\in C$ , iet $C(v)=$ { $u|u\in C\backslash \{0\}$ , Supp(w) Supp(v)}. Checking whether
a codeword is a zero neighbor or not is examining whether the dimension of $C(v)$ ,denoted by $\dim(C(v))$ , is zero or not [2]. For $v\in C$ and with, let
{ ( , , , $u_{n})\in C|u_{j}=v_{j}$ with} and $\mathrm{C}(v, i)=\{u|u\in \mathrm{S}(v, i)$ , Supp(w)Supp(v). A typical implimentation to check whether is azero neighbor or not computes,, , wherefor. For any,,
. That is, if we generate
once, we does not needto generate
for eachlater. By this, the computational complexity is
reduced. We should choose 2 properly, say $n/2$ or $n/4$ , in order to makelarge$\subseteqarrow$$v$$1\leq \mathrm{i}\leq n$$i$$u_{1}$$u_{2}$$1\leq j\leq \mathrm{i}$$\ldots$$\mathrm{C}(v, \mathrm{i})$$u’\in \mathrm{S}(v, \mathrm{i})$$\cap$$\cap\{1, \ldots , \mathrm{i}\}\}$$\{1, \ldots, \mathrm{i}\}\subseteq$$u$$\mathrm{S}(v, \mathrm{i})=$$\mathrm{C}(u, \mathrm{i})=\mathrm{C}(u’, i)$$\mathrm{C}(u, i)$$v$$\mathrm{i}=1,2$$\ldots$$n$$\mathrm{C}(v, n)=\mathrm{C}(v)$$\mathrm{C}(u, \mathrm{i})$$u\in \mathrm{S}(v, \mathrm{i})$$\mathrm{S}(v, \mathrm{i})$157small, To obtain, we use the trellis structure of cosets.
andThis method does not make the space complexity much larger, since a codeword inis generated successively. The advantage of this method depends on the code.
For extended binary primitive BCH codes, permuting the symbol positions of codewords
larger [9].
properly makes
It is not easy to estimate precisely how the computational complexity is reduced.
extended BCH code. In
We will estimate the effect roughly in the case of tlle
this case, tlle $(128, 29)$ code is chosen as the subcode and the number of representativecodewords randomly
codewords by choosing
cosets is 258. We pick up
from each of the 258 representative coset. For every codeword in such codewords, we
is found out to be zero or not. Then, theexamined a position at which thefromaverage was 100. Assuming that the complexity of obtaining, we estimated the relative computational
is proportional to the dimension of:complexity to that without using the above technique when is chosen as.
$((100-\mathrm{i}_{0})/100)^{2}+(1-((100-\mathrm{i}_{0})/100)^{2})/2^{k_{s}}$ , whereis the dimension of
It turned out that the complexity would reduced mostly by 1/2 for $\mathrm{i}=32,46$ , and 47.
code. Actually, for the $(128, 50)$ extended
Therefore, we choose 32 as for the
BCH code and the $(128, 29)$ extended BCH subcode, the complexity is reduced by about$\mathrm{C}(u, \mathrm{i})(u\in \mathrm{S}(v, i))$$\mathrm{S}(v, \mathrm{i})$$\mathrm{S}(v, \mathrm{i})$$\mathrm{S}(v, i)$$(12\mathrm{S}, 50)$$2^{15}$$2^{15}\cross 258$$v$$\dim(\mathrm{C}(v))$$\mathrm{C}(v, \mathrm{i}+1)$$\mathrm{C}(v, \mathrm{i})$$\mathrm{C}(v, i)$$\mathrm{i}(0\leq i\leq n)$$\mathrm{i}_{0}$$\mathrm{S}(v, \mathrm{i}_{0})$$k_{s}$$(12\mathrm{S}, 50)$$\mathrm{i}$1/2.

In the proposed algorithm, since the codewords that need to be checked are generated. If the dimension
in a coset is used instead ofcoset by coset, the subset ofof the subcode is small, may become small and the effect of using the trellis structure issmall. We should choose the subcode considering the effect of using the trellis structure.
$\mathrm{S}(v, i)$$\mathrm{S}(v, \mathrm{i})$$k_{s}$

5

Relations of Local Weight Distributions

5.1

General relation, and its even weight
Consider a binary linear code of length , its extended code
be the Hamming weight of and. For a codeword $v\in C$ , let
subcodeis obtained from by adding the, that is,
be the corresponding codeword inover-all parity bit.
if $v\in C$ can be represented as $=v_{1}+v_{2}$ , where , $v_{2}\in C$ alld
, is said to be decomposable. obtain Lemma 1, is not a zero neigh bor if
Supp(v2)
with respect toand only if is decomposable. To consider a relation between andzero neighborship, for even weight codewords, we refine the notion, decomposable, andintroduce only-odd-decomposable and even-decomposable.
$C$$C_{\mathrm{e}\mathrm{x}}$

$n$

$v$

$\mathrm{w}\mathrm{t}(v)$$v^{(\mathrm{e}\mathrm{x})}$$C_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}}$$v$$v^{(\mathrm{e}\mathrm{J}\mathrm{C})}$$C_{\mathrm{e}\mathrm{x}}$$\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}(v_{1})\cap$$v$$=\emptyset$

$v$

$v$

$v_{1}$$v$$C$$C_{\mathrm{e}\mathrm{x}}$. That is, v is not
Definition 5 Let v $\in C$ be a decomposable cod eword with evena zero neighbor in C. v is said to be $only- odd- decomposabfe_{2}$ if all the decomposition of$\mathrm{w}\mathrm{t}(v)$158
Table 1: Zero neighborship ofin its even weight subcode.

in a linear block code,$v$

is of the form $v_{1}+v_{2}$ with the odd weight codewords
to be even-decomposable.

$v$

in its extended code, and$v_{\mathrm{e}\mathrm{x}}$$v_{1}$

and$v_{2}$. Otherwise,

$v$

$v$

is said

is even-decomposable, there is a decomposition of , $v_{1}+v_{2}$ such thatbothandare even. The relation between andwith respect to zeroneighborship is given in the following theorem, which is also summarized in Table 1.
When

$v$

$\mathrm{w}\mathrm{t}(v_{1})$Theorem 5$v$

1. For a zero neighbor v in C,

2. For a codeword(a) When$C$$\mathrm{w}\mathrm{t}(v_{2})$$v$$\mathrm{w}\mathrm{t}(v)$is a zero neighbor in$v^{(\mathrm{e}\mathrm{x})}$which is not a zero neighbor inis old,$v^{(\mathrm{e}\mathrm{x})}$(b) Whenis even,
odd-lecomposable in .

$C$

$C_{\mathrm{e}\mathrm{x}}$.

, the following ) and ) hold.

a zero neighbor in

$b$

$a$

is not a zero neighbor in$v^{(\mathrm{e}\mathrm{x})}\iota s$$\mathrm{w}\mathrm{t}(v)$$C_{\mathrm{e}\mathrm{x}}$$C_{\mathrm{e}\mathrm{x}}$$C_{\mathrm{e}\mathrm{x}}$.

if and only if$v$

is only-$C$

For the local weight distributions of a code and its extended code, we have thefollowing theorem, which is a direct consequence of Theorem 5.
Theorem 6 if there is no only-odd-decomposable codeword in C,$L_{2i}(C_{\mathrm{e}\mathrm{x}})$$=$$L_{2i-1}(C)+L_{2i}(C)$ ,$0\leq i\leq n/2$ .

(7)Prom Theorem 6, the local weight distributions ofare obtained from that of. Next, we give a useful sufficient condition rm der which no only-odd-decomposable
codeword exists.
$C_{\mathrm{e}\mathrm{x}}$$C$

Theorem 7 If all the weights of codewords indecomposable cod ernont exists in C.

$C_{\mathrm{e}\mathrm{x}}$are multiples of four, no only-odd-

1S9
For example, all the weights of codewords in the $(128, k)$ extended primitive BCH
code with $k\leq 57$ are multiples of four. The parameters of Reed-Muller codes with which
all the weights of codewords are multiples of four are given by Corollary 13 of Chapter
15 in [15]. The third-order Reed-Muller code of length 128, 256, and 512 are true for thecase.

for these codes can be obtained from
Although the local weight distribution ofthat of by using Theorem 6, what we need is a method for obtaining the local weight. We need to know the number of zero neighbors with
distribution of from that ofparity bit one. In the next section, we will show a method to obtain the number of zeroneighbors with parity bit one for a class of transitive invariant codes.
. Thisandholds between
andA similar relation as that between
relation is given in Theorem 8.
$C_{\mathrm{e}\mathrm{x}}$

$C$

$C$

$C_{\mathrm{e}\mathrm{x}}$$C$

Theorem 8$C$$C_{\mathrm{e}\mathrm{x}}$1. For an even weight zero neighbor v in

$C_{f}$$C_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}}$v is a zero neighbor in

2. For an even weight codeword which is not a zero neighbor inneighbor if and only if is only-odd-decomposable in .
$v$

$C$

,

$v$

$C_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}}$.

is a zero

$C$

$v$

From Theorem 8, we have Theorem 9.

Theorem 9 if there is no only-odd-decomposable codeword rn$L_{2i}(C_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}})$

5.2

$=$

$L_{2i}(C)$,$C_{2}$$0\leq \mathrm{i}\leq n/2$

(8).

Relation for transitive invariant extended codes

A Transitive invariant code is the code which is invariant under a transitive group of
permutations. A group of perm utations is said to be transitive if for any two symbols
in a codeword there exists a permutation that interchanges them [16]. The extended
primitive BCH codes and Reed-Muller codes are transitive invariant codes. For a tranisand, a relation between the (global) weight distributions ofsitive invariant
presented in Theorem 8.15 in [16]. A similar relation holds for local weight distribution.
The following lemma can be proved in a similar way as the proof of Theorem 8.15.
$C$$C_{\mathrm{e}\mathrm{x}}$$C_{\mathrm{e}\mathrm{x}}$is a transitive invariant code of length $n+1$ , the number of zero neighLemma 5 if.
bors with parity bit one is$C_{\mathrm{e}\mathrm{x}}$$\frac{w}{n+1}L_{w}(C_{\mathrm{e}\mathrm{x}})$zero neighbors with weight whose parity
It is clear that there are
bit is zero from this lemma. The following theorem is obtained from Theorem 5 andLemma 5.
$\frac{n+1-w}{n+1}L_{w}(C_{\mathrm{e}\mathrm{x}})$

$u$ )

180
Theorem 10 if$C_{\mathrm{e}\mathrm{x}}$is a transitive irvvanant code of length $n+l$ ,for odd,$L_{i}(C)$$=$$\frac{\mathrm{i}+1}{n+1}L_{i+1}(C_{\mathrm{e}\mathrm{x}})$$L_{i}(C)$$\leq$$\frac{n+1-\mathrm{i}}{n+1}L_{i}(C_{\mathrm{e}\mathrm{x}})$,for even$\mathrm{i}$

,
$i$

(9)

(10)

.

If there is no only-odd-decomposable codeword in a transitive invariant codeequality of (10) holds. That is, in this case, we have that
$L_{i}(C)$$=$$\frac{n+1-\mathrm{i}}{n+1}L_{\dot{\mathrm{z}}}(C_{\mathrm{e}\mathrm{x}})$,for even$\mathrm{i}$.

$C_{\mathrm{e}\mathrm{x}}$

, the

(10)

Therefore, for a transitive invariant code
having no only-odd-decomposable codeby using
word in , the local weight distributions of can be obtained from that of(9) and (11) in Theorem 10. After computing the local weight distribution of , that ofcan be obtained by using Theorem 9.
$C_{\mathrm{e}\mathrm{x}}$

$C$

$C$

$C_{\mathrm{e}\mathrm{x}}$$C$$C_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}}$6Obtained Local Weight Distributions

As discussed in the previous section, the local weight distributions of the $(127, k)$ primitive
BCH codes for $k\leq 57$ , the unctured third-order Reed-Muller codes of length 127 255,
and 511, and their even weight subcodes are obtained from those of the corresponding
extended codes by using Theorems 9 and 10. The obtained local weight distributions
are presented in Table 2. Since the local weight distribution for the $(128, 57)$ extended
primitive BCH code and the third-order Reed-Muller code of length 256 are unknown,
only the local weight distributions of the $(127, k)$ primitive BCH codes for $k=36$ , 43, 50,
the punctured third-order Reed-Muller code of length 127 are given in the tables.
$\mathrm{p}$7Conclusion

In this resum , some of our results on the local weight distribution are given. An algorithm is shown for computing the local weight distribution of a code which are closed
under a group of permutations. The algorithm uses an invariance property under the
automorphism group. This property is applied to the set of cosets of a subcode. Somerelations between local weight distributions of a binary linear code, its extended code,and its even weight subcode are presented. The local weight distributions of the $(127, k)$primitive BCH codes for $k=36,43,50$ , the punctured third-order Reed-Muller code oflength 127 and their even weight subcodes are presented.
If the local weight distribution of the $(128, 57)$ extended primitive BCH code and thethird-order Reed-Muller code of length 256 are obtained, we can obtain the local weight
distributions of the $(127, 57)$ primitive BCH code, the punctured third-order Reed-Muller
code of length 255 and their even weight subcodes$\mathrm{e}$1el
BCH codes for $k=$
Table 2: The local weight distributions of the $(127, k)$$36,43$ , and 50 and the punctured third-order Reed-Muller code of length 127 .
$\mathrm{p}\mathrm{r}\mathrm{i}_{\mathrm{I}}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}$$(127, 43)$ BCH code$(127, 36)$ BCH code
$w$

31
32
35
36
39
40
43
44
47
48
51
52

55
56
59
60
63
64
67
68
71
72
75
76
79
$3183807976757184w$

so

83
84
87
88
$8\mathrm{S}$$L_{\mathfrak{U}}$$(127, 50)$ BCH code$(127, 64)$ punaRM code,$L_{u\prime}2,667$

2,667
8,001
4,572
11,684$\mathrm{S},001$

640,080
1,408,176
12,220,956
23,330,916
132,560,568
220,934,280
220,934280}
823,921,644
1,204,193,172
1,204,193,
172
3,157,059,472
4,059,076,464
4,059,076,464
7,022,797,740
7,959,170,772$\ovalbox{\tt\small REJECT} 11222233333444485853079476349959‘ 1685005975633920073513003585380352046223099536138240433259718804643840917\frac{9}{}48924998144061.3027962101504550978982136322233680918464177893639488824440896007684345088460188856313889736682677511\mathrm{S}115231949565260149555251218602288622075904632586645221710_{\vee}^{\mathrm{Q}}336060148100822636691456056986014146735636480557668998919\mathit{0}5495040642586645221710\sim 93360591306771964441395200w,L_{w}$$\ovalbox{\tt\small REJECT} 3333444483,590,325,676)7610499335,164’ 8404380,144,258,7603199,123,183,160023_{\}}185,148,448910538,703,8405310,454,.802214,55915314,853_{?}051521992,309,104,344472,154,195,406_{r}10436793,38449460131,384|112_{?}\frac{\eta}{}07’ 62859115,927,157,8302605665,938,862,854’ 5485551,28^{\frac{5}{\mathrm{D}}},782,220,204\epsilon 8115_{\mathfrak{l}}816_{1}2^{95032,060}5113,633,106,229,28864158486,906,38547263158486,906,385’ 47228146,0502740,8947250,491,207_{7}614_{2}7927164917,2\tilde{6}6,933_{7}3047515,345,182,164’ 03267131,258,388369668864wL_{\omega}\})))))))))$$\ovalbox{\tt\small REJECT} 333444828,062,,422)792\mathrm{G},980’ 3679204716)837,45375242,967,005,49631554145,73640181,185,312982,356_{\}96066_{?}332_{\gamma}72852478,02455400,716,792,67252155,632,998,36051106,485,735,72071515,097,101,37668905599,052,400671,026,345,592,720641,238,334,929,472631,238,334,929,472601026,361,189,33659905,612,814,12056515_{\}}207,304,8643293,3453131,11576106_{)}183681_{)}9687\tilde{5}155_{\mathrm{J}}191535,1847^{9}40_{1_{1}617,588,840}84847’ 308,440838010,18\mathrm{S},220,608680wL_{w})0_{7}631,078,848\}\})))\}$

9742066,’368}
9742066,368}

9,742,066,368
170,772
7,959,170,772
7,959,
7,022,797,740$4_{7}059,071,892$

3,157,055,916
1,204,193,172
823,921,644$217_{\gamma}627,200$

130,576,320
130, $c^{r}76,320$
23,330,916
23330916},
12,220,956$1,408_{l}176$

640,080

References[1] E. Agrell, “On the Voronoi Neighbor Ratio for Binary Linear Block Codes,’\rangle IEEE
Trans. Inform. Theory, vo1.44, no.7, pp.3064-3072, Nov. 1998.

[2] E. Agrell, “Voronoi regions for binary linear block codes,” IEEE Trans. Inform. Theory, vo1.42, no.l, pp.310-316, Jan. 1996.
[3] M. Mohri, and . Morii, “On computing the local distance profile of binary cyclic
codes,” Proc. of ISITA2002, pp.415-418, Oct. 2002.
$\mathrm{h}/\mathrm{I}$method for computing the local weight[4] M. Mohri, Y. Honda, and M.
distribution of binary cyclic codes,” IEICE Trans. Fundamentals (Japanese Edition),
vol.J86-A, no. 1, pp.60-74, Jan. 2003.
$\mathrm{M}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{i}/’ \mathrm{A}$[5] G.D. Forney, Jr., “Geometrically uniform
vo1.44, no.5, pp.1241-1260 Sept, 1998.

codes,” IEEE Trans. Irtforrn. Theory,

182[6] A. Ashikhmin and A. Barg, “Minimal vectors in linear codes,” IEEE Trans. Inform.

Theory, vo1.44, no.5, pp.2010-2017, Sept. 1998.

[7] T. Fujiwara and T. Kasami, “The weight distribution of (256, k) extended binary
primitive BCH codes with k $\leq 63$ and k $\geq 207,$ IEICE Technical Report, IT97-46,
Sept. 1997.
)’[8] T. Sugita, T. Kasami, and T. Fujiwara, “The weight distribution of the thirdorder Reed-Muller codes of length 512,” IEEE Trans. Inform. Theory, voL42, no.5,
pp. 1622-1625 Sept. 1996.

[9] T. Kasami, T. Tanaka, T. Fujiwara, and S. Lin, “On complexity of trellis structureof linear block codes,” IEEE Trans. Inform. Theory, vo1.44, no.3, pp.1057-1064,
May. 1993.
[10] X. Hou,$\zeta‘ \mathrm{G}\mathrm{L}(m,$2) acting on $R(r, m)/R(r$ –1, m) ,” Discr. Math., 149, pp.99-122,

1996.
[11] K. Yasunaga and T. Fujiwara, “An algorithm for computing the local distance profile of binary linear codes closed under a group of permutations,” IEICE Technical
Report, IT2003-47, Sept. 2003.

[12] K. Yasunaga and T. Fujiwara, “The local weight distributions of the (128, 50) extended binary primitive BCH code and (128, 64) Reed-Muller code,” IEICE Technical Report, IT2004-19, Jul. 2004.
[13] K. Yasunaga and T. Fujiwara, “An algorithm for computing the local weight distribution of binary linear codes closed under a group of perm utations,” Proc. of
ISITA2004, pp.846-851, Oct. 2004.
[14] K. Yasunaga and T. Fujiwara, “Relations among the Local Weight Distributions of
a Linear Block Code, Its Extended Code and Its Even Weight Subcode,” SITA2004,
pp.559-562, Dec. 2004.

[15] F.J. MacWilliams and N.J.A. Sloane, The theory of error-correcting codes, NorthHolland, 1977.
[16] W.W. Peterson and E.J. Weldon, Jr., Error-cor recting codes, 2nd Edition, MIT
Press, 1972