- Source: Griesmer bound
In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension k and minimum distance d.
There is also a very similar version for non-binary codes.
Statement of the bound
For a binary linear code, the Griesmer bound is:
n
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
{\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}
Proof
Let
N
(
k
,
d
)
{\displaystyle N(k,d)}
denote the minimum length of a binary code of dimension k and distance d. Let C be such a code. We want to show that
N
(
k
,
d
)
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
{\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}
Let G be a generator matrix of C. We can always suppose that the first row of G is of the form r = (1, ..., 1, 0, ..., 0) with weight d.
G
=
[
1
…
1
0
…
0
∗
∗
∗
G
′
]
{\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}
The matrix
G
′
{\displaystyle G'}
generates a code
C
′
{\displaystyle C'}
, which is called the residual code of
C
.
{\displaystyle C.}
C
′
{\displaystyle C'}
obviously has dimension
k
′
=
k
−
1
{\displaystyle k'=k-1}
and length
n
′
=
N
(
k
,
d
)
−
d
.
{\displaystyle n'=N(k,d)-d.}
C
′
{\displaystyle C'}
has a distance
d
′
,
{\displaystyle d',}
but we don't know it. Let
u
∈
C
′
{\displaystyle u\in C'}
be such that
w
(
u
)
=
d
′
{\displaystyle w(u)=d'}
. There exists a vector
v
∈
F
2
d
{\displaystyle v\in \mathbb {F} _{2}^{d}}
such that the concatenation
(
v
|
u
)
∈
C
.
{\displaystyle (v|u)\in C.}
Then
w
(
v
)
+
w
(
u
)
=
w
(
v
|
u
)
⩾
d
.
{\displaystyle w(v)+w(u)=w(v|u)\geqslant d.}
On the other hand, also
(
v
|
u
)
+
r
∈
C
,
{\displaystyle (v|u)+r\in C,}
since
r
∈
C
{\displaystyle r\in C}
and
C
{\displaystyle C}
is linear:
w
(
(
v
|
u
)
+
r
)
⩾
d
.
{\displaystyle w((v|u)+r)\geqslant d.}
But
w
(
(
v
|
u
)
+
r
)
=
w
(
(
(
1
,
⋯
,
1
)
+
v
)
|
u
)
=
d
−
w
(
v
)
+
w
(
u
)
,
{\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),}
so this becomes
d
−
w
(
v
)
+
w
(
u
)
⩾
d
{\displaystyle d-w(v)+w(u)\geqslant d}
. By summing this with
w
(
v
)
+
w
(
u
)
⩾
d
,
{\displaystyle w(v)+w(u)\geqslant d,}
we obtain
d
+
2
w
(
u
)
⩾
2
d
{\displaystyle d+2w(u)\geqslant 2d}
. But
w
(
u
)
=
d
′
,
{\displaystyle w(u)=d',}
so we get
2
d
′
⩾
d
.
{\displaystyle 2d'\geqslant d.}
As
d
′
{\displaystyle d'}
is integral, we get
d
′
⩾
⌈
d
2
⌉
.
{\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .}
This implies
n
′
⩾
N
(
k
−
1
,
⌈
d
2
⌉
)
,
{\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}
so that
N
(
k
,
d
)
⩾
d
+
N
(
k
−
1
,
⌈
d
2
⌉
)
.
{\displaystyle N(k,d)\geqslant d+N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right).}
By induction over k we will eventually get
N
(
k
,
d
)
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
{\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}
Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity
⌈
⌈
a
/
2
k
−
1
⌉
2
⌉
=
⌈
a
2
k
⌉
{\displaystyle \left\lceil {\frac {\left\lceil a/2^{k-1}\right\rceil }{2}}\right\rceil =\left\lceil {\frac {a}{2^{k}}}\right\rceil }
for any integer a and positive integer k.
Bound for the general case
For a linear code over
F
q
{\displaystyle \mathbb {F} _{q}}
, the Griesmer bound becomes:
n
⩾
∑
i
=
0
k
−
1
⌈
d
q
i
⌉
.
{\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{q^{i}}}\right\rceil .}
The proof is similar to the binary case and so it is omitted.
See also
Elias Bassalygo bound
Gilbert-Varshamov bound
Hamming bound
Johnson bound
Plotkin bound
Singleton bound
References
J. H. Griesmer, "A bound for error-correcting codes," IBM Journal of Res. and Dev., vol. 4, no. 5, pp. 532-542, 1960.
Kata Kunci Pencarian:
- Griesmer bound
- Hamming bound
- Gilbert–Varshamov bound
- Singleton bound
- Plotkin bound
- Johnson bound
- Introduction to the Theory of Error-Correcting Codes
- Southeastern Ceremonial Complex
- American Bottom
- Angel Mounds
