Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
Ξ(K) =
1
|K|
n
X
j=0
(η
j
− ω(j)|K|)
2
ω(j)
=
1
|K
⊥
|
n
X
j=1
ν
j
2
ω(j)
,
ν
j
K
⊥
j
K
0
(s) =
P
n
t=0
K
(p,n)
w
(s) 0
s = 1, . . . , n K
0
(0) = p
n
K
0
(s) = Ω(s, 1, 1)
Ω(s, x, y) = (y −x)
s
(x + (p − 1)y)
n−s
=
n
X
w=0
K
(p,n)
w
(s)x
w
y
n−w
.
ν
0
− ω(0)K
0
(0) = 0 ν
0
= 1
P (s) = K
0
(s) α
s
=
1, s = 0, . . . , n ¤
Ξ
1
(K) =
1
|K|
n
X
s=0
³
η
s
−
³
1 + ν
n
(−1)
s
(p−1)
s
´
ω(s)|K|
´
2
ω(s)
=
1
|K
⊥
|
n−1
X
t=1
ν
t
2
ω(t)
,
ν
n
K
⊥
K
1
(s) =
P
n
t=0
³
−
1
p−1
´
t
K
(p,n)
t
(s)
K
1
(s) = Ω(s, 1, −
1
p−1
)
K
1
(s) =
(
0, s = 0, . . . , n − 1 ,
p
n
(p−1)
n
, s = n
.
P (x) = K
0
(x) + ν
n
K
1
(x) ¤
p = 2 ν
n
= 1
Ξ
1
(K) =
1
|K|
[
n
2
]
X
s=0
(η
2s
− 2ω(2s)|K|)
2
ω(2s)
=
1
|K
⊥
|
n−1
X
t=1
ν
t
2
ω(t)
.
¤
p = 2 ν
n
= 1
ν
2j+1
= 0
P (x) =
1
|K|
n
X
s=0
η
s
K
(p,n)
s
(x)
ω(t)
,
(ν
t
− ω(t)P (t))
2
= 0, t = 0, . . . , n.
ν
t
η
s
Ξ(K)
Ξ(K)
η(K) K
k = dim K n − k
η(K)
K K
⊥
M Ξ
1
(K) Ξ(K)
K k Ξ(K)
K M Ξ
1
(K) ∼ Ξ
1
(K
m
)
η(K
m
)
M
k
= M Ξ(K), k = dim K
K
Ξ(K)
K K
⊥
K
R
1
= R
⊥
m−2
K = R
m−2
η(R
⊥
m−2
)
1
|R
1
|
n−1
X
t=1
ν
t
2
ω(t)
<
|R
1
|
ω(
n
2
)
.
s ≤
n
2
1
|R
m−2
|ω(2s)
(η
2s
− 2ω(2s)|K|)
2
<
1
|R
m−2
|
[
n
2
]
X
j=0
(η
2j
− 2ω(2j)|R
m−2
|)
2
ω(2j)
.
|RM
1
| · |R
m−2
| = 2
n
(η
2s
− 2ω(2s)|R
m−2
|) | <
s
2
n
ω(2s)
ω(
n
2
)
.
ω
³
n
2
´
= 2
−n
µ
n
n
2
¶
<
1
C
0
√
n
,
C
0
C
1
n
1
4
¡
n
2s
¢
1
2
C
1
=
√
C
0
|(η
2s
− 2ω(2s)|R
m−2
|) | < C
1
n
1
4
s
µ
n
2s
¶
.
n 2ω(2s)|R
m−2
| =
(
n
2s
)
n
> C
1
n
1
4
q
¡
n
2s
¢
, s = 2, . . . ,
n
2
−2
η
2s
= 2ω(2s)|R
m−2
|(1 + ²
n
) =
¡
n
2s
¢
n
(1 + ²
n
), s = 2, . . . ,
n
2
− 2,
²
n
→ 0 n → ∞
x x =
n
2
F
p
T r(x), x ∈ F
q
, q = p
l
F
q
F
p
r = p
χ(x) = exp
µ
2π i T r(x)
p
¶
, i =
√
−1,
F
q
F
q
1 p− χ(x+y) = χ(x)χ(), x, y ∈
F
q
f(x) ∈ F
q
[x]
T r(f(x)) x ∈ F
q
T r(f(x)) 6≡ const
T
f
=
¯
¯
¯
¯
¯
¯
X
x∈F
q
χ(f(x))
¯
¯
¯
¯
¯
¯
≤ (r − 1)q
1
2
, r = deg f(x) .
r − 1 ≤
√
q
K(B
(d)
A
) q
B = B
(d)
A
A = F
q
BCH(B
(d)
A
) = K(B
(d)
A
)
T
F
q
p
F
p
K
⊥
(B
(d)
A
) K(B
(d)
A
)
a
f
= (f(α
1
), . . . , f(α
q
))
F
p
a
f
= (T r(f(α
1
)), . . . , T r(f(α
q
))), deg f ≤ d − 2,
BCH
⊥
(B
(d)
A
) BCH(B
(d)
A
)
ω = {ω
1
, . . . , ω
l
} F
q
F
r
α ∈ F
q
α =
P
l
j=1
a
j
ω
j
, a
j
∈ F
p
α = (a
1
, . . . , a
l
) α F
q
ω
B
(d)
A
α
s
i
α
s
i
T
b
B
(d)
A
F
p
b
B
(d)
A
BCH
⊥
(B
(d)
A
)
L
d
= {a
f
|deg f ≤ d−2}
b
B
(d)
A
b ∈ BCH(B
(d)
A
) T r(x) hb, a
f
i = 0
a
f
∈ L
d
L
d
⊆ BCH
⊥
(B
(d)
A
)
l × q− B
(d),s
A
= (a
s
1
T
, . . . , a
s
q
T
), 0 ≤ s ≤ d −
2 B
(d),s
A
{a
f
|f(x) = ax
s
} BCH
⊥
(B
(d)
A
) ⊆ L
d
¤
α
f
∈ BCH
⊥
(B
(d)
A
) Tr(f(x)) 6≡ const
p − 1
p
(q + (d − 3)
√
q) ≥ w(α
f
) ≥
p − 1
p
(q − (d − 3)
√
q) .
wt(α) α = (a
1
, . . . , a
n
) ∈ F
n
p
wt(α) = q −
n
X
s=1
1
p
Ã
p−1
X
j=0
exp
µ
2π i ja
s
p
¶
!
.
w(α
f
) = q −
1
p
X
x∈F
q
p−1
X
j=0
χ
j
(f(x)) =
p − 1
p
q −
1
p
p−1
X
j=1
X
x∈F
q
χ
j
(f(x))
.
¤
p > 2 K = BCH(B
(d)
A
) p− q =
p
l
d
B
(d)
A
, A = F
q
r
d
= 1 + l ·
³
d − 2 −
h
d−2
p
i´
BCH
⊥
(B
(d)
A
)
d = const, q → ∞, s > 2
µ
d − 2 −
·
d − 2
p
¸¶
η
s
= η
s
(BCH(B
(d)
A
))
BCH(B
(d)
A
)
η
s
= p
−r
d
((p − 1)
s
+ (−1)
s
(p − 1))
µ
q
s
¶
(1 + ε
s,q
) ,
ε
s,q
³ q
−
1
4
p
r
d
(p − 1)
−s
µ
q
s
¶
−
1
2
→ 0 q → ∞.
ν
q
= p − 1 α
f
∈
BCH
⊥
(B
(d)
A
) T r(f(x)) 6≡ const w(α
f
) < q
w(α
f
) = q T r(f(x)) ≡ const ∈ F
p
T r(x) p
l−1
< q
x ∈ F
q
a ∈ F
q
T r(a) = b 6= 0, b ∈ F
p
c ∈ F
p
\{0} f(x) = a T r(cf(x)) = cT r(f(x)) = cb
BCH
⊥
(B
(d)
A
)
p − 1 α
f
q f (x)
f(x) = ac
|K||K
⊥
| = p
q
s
µ
η
s
−
µ
1 + ν
q
(−1)
s
(p − 1)
s
¶
ω(s)|K|
¶
2
< |K|ω(s)Ξ
1
(K) =
1
|K
⊥
|
2
µ
q
s
¶
n−1
X
t=1
ν
t
2
ω(t)
= R
d
.
R
d
ν
t
= 0,
¯
¯
¯
¯
t −
(p − 1)q
p
¯
¯
¯
¯
>
p − 1
p
(d − 3)
√
q .
P
n−1
t=1
ν
t
2
< |K
⊥
|
2
R
d
≤
1
ω
min
|K
⊥
|
2
µ
q
s
¶
n−1
X
t=1
ν
t
2
<
¡
q
s
¢
ω
min
,
ω
min
= min ω(t) min t
¯
¯
¯
t −
(p−1)q
p
¯
¯
¯
≤
p−1
p
(d − 3)
√
q
min ω(t)
h
(p−1)q
p
− (d − 3)
√
q,
(p−1)q
p
+ (d − 3)
√
q
i
t
ω
min
=
1
p
q
min
µ
(p − 1)
t
0
µ
q
t
0
¶
, (p − 1)
t
1
µ
q
t
1
¶¶
,
t
0
=
p−1
p
¡
q − (d − 3)
√
q
¢
t
1
=
p−1
p
¡
q + (d − 3)
√
q
¢
d = const, q → ∞
ω
min
=
1
C
d
√
q
,
C
d
d
d = const, q → ∞ K
⊥
r
d
= 1 +
³
d − 2 − l ·
h
d−2
p
i´
ω(s)|K| =
¡
q
s
¢
p
r
d
.
ν
q
= p − 1
¯
¯
¯
¯
µ
η
s
− p
−r
d
((p − 1)
s
+ (−1)
s
(p − 1))
µ
q
s
¶¶
¯
¯
¯
¯
<
p
R
d
<
s
C
d
√
q
µ
q
s
¶
= Q
d,s
.
p = const, q → ∞
ε
s,q
=
Q
d,s
p
−r
d
((p − 1)
s
+ (−1)
s
(p − 1))
¡
q
s
¢
³ q
1
4
p
r
d
(p − 1)
−s
µ
q
s
¶
−
1
2
, p > 2, s > 1.
d = const r
d
= 1 + l ·
³
d − 2 −
h
d−2
p
i´
= const
0
s > 2
³
d − 2 −
h
d−2
p
i´
ε
s,q
→ 0 q → ∞.
¤
p > 2
p = 2 s > q −
2
³
d − 2 −
h
d−2
p
i´
s q
p = 2
η
s
η
2s
= 2
−r
d
µ
q
2s
¶
(1 + ε
2s,q
) s d ≤ s ≤ q −d,
η
t
= 0, t,
|ε
2s,q
)| ³ q
1
4
2
r
d
¡
q
2s
¢
−
1
2
BCH(B
(d)
A
) d
r
d
= 1+l·
¡
d − 2 −
£
d−2
2
¤¢
= 1+l·
d−2
2
BCH
⊥
(B
(d)
A
)
s s = d s = q − d ¤
d = const
t, 0 < t < q η
t
6= 0
p > 2 t
t = d η
t
s
s
η
s
≈ p
−r
d
(p − 1)
s
¡
q
s
¢
p q
q
s
s η
s
≈ p
−r
d
(p − 1)
s
¡
q
s
¢
d → ∞ q → ∞
d, s, q |ε
s,q
| → 0 q → ∞
S = S(X, R
0
, . . . , R
m
)
X m + 1
X×X m+1 R
0
, . . . , R
m
R
0
= {(x, x)|x ∈ X}
(x, y) ∈ X × X r
i,j
(x, y) (x, z), (z, y) (x, z) ∈
R
i
, (z, y) ∈ R
j
(x, y) ∈ R
k
r
i,j
(x, y) = r
k
i,j
R
k
(x, y)
R
T
j
= {(y, x)|(x, y) ∈ R
j
}
R
0
, . . . , R
m
R
T
j
= R
j
0
j
0
X X ×
X S X
X
S
r
k
i,j
= r
k
j,i
S
S
R
T
j
= R
j
j = j
0
S
r
0
s,s
= v
s
R
s
(x, y) ∈ X × X x ∈ X
R
s
S
H
(G) v
s
C
s
S
R
0
R
1
m = 1
R
0
= {(a, a)|a ∈ X}, R
1
= {(a, b)|a, b ∈ X, b 6= a} = X × X r R
0
.
H
n
2
m+1 = n +1 X =
F
n
, |F | = 2, n−
F
2
n−
R
j
(x, y), x, y ∈ F
n
2
d(x, y)
j
d(x, y) = k i + j − k
r
i,j
(x, y) = r
k
i,j
=
µ
n − k
r
¶µ
k
k − j + r
¶
=
µ
n − k
r
¶µ
k
j − r
¶
, r =
i + j − k
2
.
d(x, y) = k i + j −k r
i,j
(x, y) =
0
R
T
j
R
j
H
n
2
H
n
q
X =
F
n
, |F | = q ≥ 2, n−
F
q
q
X = {0, 1, . . . , 6}
mod 7 S
m = 2
R
0
= {(a, a)|a ∈ X}, R
+
= {(a, b)|b − a ∈ {1, 2, 4}}, R
−
= {(a, b)|b − a ∈ {3, 5, 6}}.
R
+
R
−
R
−
R
+
R
+
(a, b)
¡
b−a
7
¢
= 1 R
−
¡
b−a
7
¢
= −1
³
a
p
´
,
a, a 6= 0, mod p
³
a
p
´
= 1 mo d p x a ≡ x
2
³
a
p
´
= −1 x