Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
f α
α 6= 0 RM
r,m
(α) = {f
α
|f ∈
d
RM
r,m
}
g ∈ RM
r−1,m
g(x) ∈
d
RM
r−1,m
g(x) + g(x + α) = 0.
dim RM
r,m
(α) RM
r,m
(α)
dim RM
r,m
(α) = dim RM
r−1,m−1
=
r−1
X
j=0
µ
m − 1
j
¶
.
f
α
f(x) ∈
d
RM
r,m
(α)
d
RM
r,m
(α)
r − 1
deg f ≤ r deg f
α
≤ r −1
σ
α
: f → f
α
, f ∈ RM
r,m
,
RM
r,m
RM
r−1,m
dim RM
r,m
(α)
A ∈ M
m
(F
2
) α = e
1
A e
1
=
(1, 0, . . . , 0) f
α
= f
0
e
1
f
0
(x) = f(xA)
f
d
RM
r,m
f
0
d
RM
r,m
dim RM
r,m
(α) = dim RM
r,m
(e
1
)
α = e
1
dim RM
r,m
(e
1
)
f(x) = x
1
x
i
2
···x
i
t
, 1 < i
2
< ··· < i
t
≤ m
f
e
1
= x
1
x
i
2
···x
i
t
+ (x
1
+ 1)x
i
2
···x
i
t
= x
i
2
···x
i
t
.
RM
r,m
(e
1
)
x
i
2
···x
i
t
, 1 < i
2
< ··· < i
t
≤ m dim
d
RM
r,m
(e
1
) = dim
d
RM
r−1,m−1
=
P
r−1
j=0
¡
m−1
j
¢
¤
f
α
∈ RM
r,m
(α) 2
m−1
f
α
(x) f
α
(x + α)
f
α
∗
2
m−1
f
α
(x) f
α
(x + α)
f
α
Φ
α
f
α
∈ RM
r,m
(α) f
α
∗
RM
r−1,m−1
g(x) ∈ RM
r−1,m
A
α
α = e
1
A
α
f
α
= f
0
e
1
f
0
(x) = f(xA)
Φ
α
g(α
j
) g(x) = (g(α
1
), . . . , g(α
2
m
)) ∈ RM
r,m
(α)
α
j
A
α
1 Φ
α
(g(x)) = g
0
(0, x
2
, . . . , x
m
)
RM
r−1,m−1
r−
f(x) ∈ R M
r,m
e ∈ F
2
m
2
f(x)
0
= f(x)+e
t t = wt(e) e
f(x)
0
f(x)
0
f(x) ∈
RM
r,m
∈ RM
r,m
f(x)
0
a
i
1
,...,i
k
, 0 ≤
k ≤ r, f(x)
f
α
f(x)
f(xA + α) f(x)
σ : x → x + α
f
α
0
f
α
f
α
0
= f(x)
0
+ f (x + α )
0
= f
α
+ e + e
α
,
f(x + α)
0
f(x)
0
σ e
α
e
σ
α
f
α
RM
r−1,m
f
α
(x) f
α
(x+α) f
α
f
α
0
RM
r−1,m
t
0
= wt(e + e
α
)
f
α
0
f
α
b
j
1
,...,j
s
f
α
(x) =
r−1
X
s=0
X
j
1
<···<j
s
b
j
1
,...,j
s
x
j
1
···x
j
s
.
f
α
(x)
b
j
1
,...,j
r−1
a
i
1
,...,i
r
f(x)
a
i
1
,...,i
r
b
j
1
,...,j
r−1
¡
m
r−1
¢
b
j
1
,...,j
s
¡
m
r
¢
a
i
1
,...,i
r
α
α
b
i
1
,...,i
r−1
a
i
1
,...,i
r
f
a
i
1
,...,i
s
, 0 ≤ s < r, f
b
f(x) =
X
i
1
<···<i
r
a
i
1
,...,i
r
x
i
1
···x
i
r
a
i
1
,...,i
r
f(x)
0
+
b
f(x) RM
r−1,m
t
RM
r,m
RM
r−1,m
r
¡
m
r
¢
t
0
f
α
RM
r−1,m
t t
0
0 ≤ t
0
≤ 2t f
α
f
RM
r−1,m
RM
r−2,m
T (r, m)
RM
r,m
T (r, m) = O((
µ
m
r
¶
3
+ Cm2
m
)T (r − 1, m)),
¡
m
r
¢
3
¡
m
r
¢
C
0
m
α
a
i
1
,...,i
r
C
00
2
m
f
α
0
α
C = C
0
C
00
T (r, m) m → ∞ r = const
2
m
RM
r,m
r = 1 r = 2
RM
1,m
r = 1 f ∈ RM
1,m
f(x) =
ha, xi + a
0
= a
1
x
1
+ ··· + a
m
x
m
+ a
0
f
α
(x) α
f
α
(x) = ha, αi = b
α
f
α
0
, f
α
∈ RM
0,m
,
f
α
0
= f(x)
0
+ f(x + α)
0
= b
α
+ e + e
α
= b
0
α
b
α
b
α
f
α
0
a
j
f
ha, α
(j)
i = b
0
α
(j)
, j = 1, . . . , m
0
,
Ω = {α
(1)
, . . . , α
(m
0
)
} F
m
2
Ω m
0
= m
a
ha, xi a
0
f
f
α
0
+ ha, xi RM
0,m
f
0
= f +e
RM
1,m
e t = wt(e) P
t
b
0
α
= b
α
1 t <
1
2
(N − C
4
√
N) C
N C
4
√
N C
√
N
f
α
0
t
0
= wt(e+e
α
) t = wt(e)
t ≈
N
2
(1 − ²), ² < 1 t
0
≈
N
2
(1 − ²
2
)
P
t,m
b
0
α
= b
α
m
α 1 t <
1
2
(N − ρ(m)
4
√
N) ρ(m)
ρ(m) ρ(m) = C
√
m
T =
O(m2
m
)
RM
2,m
RM
2,m
r = 2 f ∈ RM
2,m
f(x) =
X
i<j
a
i,j
x
i
x
j
+ a
1
x
1
+ ··· + a
m
x
m
+ a
0
.
f
α
(x) α
f
α
(x) = f(x + α) + f(x) = a
0
+ f (α) +
m
X
i=1
b
i
(α)x
i
,
b
i
(α) =
P
m
j=1
a
∗
i,j
α
j
a
j,j
= 0 a
∗
i,j
=
(
a
i,j
, i < j ,
a
j,i
, i > j
.
f
α
0
, f
α
∈ RM
1,m
,
RM
1,m
O(m2
m
) f
α
?
, f
α
?
∈ RM
1,m
,
f
α
0
b
?
i
(α), i = 1, . . . , m,
f
?
α
(x) =
P
m
i=1
b
?
i
(α)x
i
+ b
0
α m
m
X
j=1
a
∗
i,j
α
j
= b
?
i
(α), i = 1, . . . , m,
a
i,j
α = e
s
= (0, . . . , 0, 1, 0, . . . , 0) s−
m
a
∗
i,s
= b
?
i
(e
s
), i = 1, . . . , m.
a
i,j
, i < j
s
¡
m
2
¢
a
i,j
, i < j m
2
b
i
(e
s
) b
i
(e
s
) = b
s
(e
i
)
b
?
i
(e
s
) 6= b
?
s
(e
i
) b
?
i
(e
s
)
b
?
s
(e
i
)
b
?
i
(e
s
) = b
?
s
(e
i
) i, s, i 6= s
a
i,j
= b
?
i
(e
s
), i < j
α
a
i,j
a
i,j
¡
m
2
¢
=
m(m−1)
2
m−1
2
α
f
α
0
, f
α
∈ RM
1,m
O(m2
m
)
f
0
= f +e
RM
2,m
RM
1,m
f
α
?
∈ RM
1,m
wt(e + e
α
) <
1
2
(N −C
r
m
1
2
√
N)
e + e
α
t
0
e t e + e
α
e
α
j
e
α
j
+α
e + e
α
α
j
α
j
+ α
t
f
α
α
j
α
j
+ α
f
α
M
2
m−1
RM
1,m−1
e
+
e
α
{e+e
α
}
M
2
m−1
e t
0
{e+e
α
}
M
t 0 ≤ t ≤ min(2t
0
, 2
m−1
), {e + e
α
}
M
t
f
α
M
0
= f
α
M
+ {e +
e
α
}
M
e t = wt(e) t <
1
2
(N − C
1
m
1
4
4
√
N)
wt(e + e
α
) <
1
2
(N −C
0
1
m
1
2
√
N) C
0
1
t <
1
2
(N − C
1
m
1
4
4
√
N) f
α
+ e + e
α
m
α a
i,j
= b
?
i
(e
s
), i < j
m t <
1
2
(N −
ρ(m)
4
√
m
4
√
N) ρ(m) ρ(m)
ρ(m) = C
4
√
m
t = wt(e)
f + e t <
1
2
(N −C
√
m
4
√
N)
f
f
α
α
α
(1)
+α
(2)
+α
(3)
= 0
f
α
(1)
+ f
α
(2)
+ f
α
(3)
= const
f
α
?
2
1+
(
m
1
)
+
(
m
2
)
1 +
¡
m
1
¢
+
¡
m
2
¢
RM
1,m
N = 2
m
O(m
2
2
m
)
r = 2
•
•
f(x)
0
= f(x) + e
f(x)
f(x)
e 1
p, 0 ≤ p <
1
2
ξ
α
, α ∈ F
m
2
, 1
p =
1−ε
2
0 q =
1+ε
2
, 1 ≥ ε ≥ 0
p q
1±ε
2
ξ
α
, α ∈ F
m
2
,
ξ ξ = (ξ
α
1
, . . . , ξ
α
N
), N = 2
m
P (ξ
α
+ ξ
β
= 1) =
1 − ε
2
2
, α 6= β.
P (f(α) + ξ
α
+ f (β) + ξ
β
= 1) =
1 − (−1)
f(α)+f(β)
ε
2
2
, α 6= β.
ξ
α
α f(x)
0
f(α) + e
α
e
α
ξ
α
Mκ
κ
M(−1)
f(α)+ξ
α
= (−1)
f(α)
ε M (−1)
f(α)+ξ
α
+f(β)+ξ
β
=
(
(−1)
f(α)+f(β)
ε
2
α 6= β
1 α = β
.
N
p
f(x)
0
N
p
= M wt(ξ) =
X
x∈F
m
2
Mwt(ξ
x
) = p2
m
= 2
m−1
(1 − ε),
N
0
p
f
α
(x)
0
f(x) = 0 α 6= 0
N
0
p
=
X
x∈F
m
2
M wt(ξ
x
+ ξ
x+α
) =
1
2
X
x∈F
m
2
M (1 − (−1)
ξ
x
+ξ
x+α
) = 2
m−1
(1 − ε
2
) = 2
m+1
pq.
N
0
p
f
α
(x)
0
f(x)
0
f
α
(x)
P M
r−1,m
f(x) P M
r,m
K n
A
K
x ∈ F
n
2
y ∈ K x
K
x
p y
0
∈ K
x = y
0
+ e e ξ
e ξ
y
0
∈ K K
P
er
(p, K) K
A
K
P
er
(p, K)
y 6= y
0
x ∈ F
n
2
X ⊆ F
n
2
d(x, X) x X
d(x, X) = min
y∈X
d(x, y).
e K
d(e, K \ {0}) ≤ wt(e),
K
d(e, z) ≤ wt(e) z ∈ K y
0
∈ K
d(e + y
0
, z + y
0
) ≤ d(y
0
, y
0
+ e) = wt(e)
y
0
+ e e
y
0
∈ K A
K
K
z + y
0
6= y
0
d(y
0
, y
0
+ e) = wt(e)
A
K
y
0
+ e e K
e A
K
y
0
y
0
+ z y
0
A
K
t
wt(ξ) = t P (p, K/wt(ξ) = t)
P
er
(p, K/wt(ξ) = t) ≤
M(t, K)
¡
n
t
¢
,
M(t, K) t K P
er
(p, K/wt(ξ) =
t)
wt(x) = s H(t, s) e t d(e, x) ≤
t
H(t, s) =
X
s
2
≤j≤t
µ
s
j
¶µ
n − s
t − j
¶
.
K
M(t, K) ≤
X
x∈K, x6=0
H(t, wt(x)) =
X
0<s≤2t
η
s
H(t, s),
η
s
s K
RM
r,m
P
er
(p, K/wt(ξ) = t), t <
N
2
,
RM
r,m
N = 2
m
dim RM
r,m
=
P
r
j=0
¡
N
j
¢
m → ∞ r = const
t =
N−λ
√
N
2
, λ > 0,
P
er
(p, K/wt(ξ) = t) ≤ C exp
2
µ
−
1
2 ln 2
λ
2
ε(r) + dim RM
r,m
¶
1
2
,
ε(r) = (2
r
− 1)
−1
C
λ = 2 ((2
r
− 1) ln 2 dim RM
r,m
)
1
2
P
er
(p, K/wt(ξ) = t) ≤ C exp
2
(−dim RM
r,m
) = C|RM
r,m
|
−1
.
RM
r,m
η
s
0 <
s < N2
−r
N(1 − 2
−r
) < s < N
M(t, K) ≤ |RM
r,m
|max H(t, s),
s [N 2
−r
, N(1 − 2
−r
)]
s
max H(t, s)
¡
N
t
¢
s
s
X
i=0
µ
s
i
¶µ
N −s
t − i
¶
=
µ
N
t
¶
.
H(t, s) =
P
s
2
≤i≤t
¡
s
i
¢¡
N−s
t−i
¢
s ∈ [N2
−r
, N(1−2
−r
)]
H(t, s)
t =
1
2
(N − λ
√
N) i =
s
2
+ j s
H(t, s)
H(t, s) =
1
2
s
X
j=0
µ
s
1
2
s + i
¶µ
N −s
1
2
(N −s −λ
√
N) − i
¶
.
¡
s
1
2
s+i
¢ ¡
N−s
1
2
(N−s−λ
√
N)−i
¢
i
H(t, s) ≤
µ
s
1
2
s
¶µ
N −s
1
2
(N −s −λ
√
N)
¶
ρ(s).
ρ(s)
ρ(s) ≤
s
2
+ 1
s
2
+ 1
ρ(s) ≤ C
1
√
N,
C
1
s
¡
2k
k−u
¢
≤ C
2
k
−
1
2
exp
2
{2kH(
k−u
2k
)} H(x) = −x log
2
x−(1−x) log
2
(1−x)
k 0 ≤ u ≤ C
3
k, 0 ≤ C
3
< 1
H(t, s) ≤ C
4
N
−
1
2
exp
2
(
s + (N −s)H
Ã
N −s −λ
√
N
2(N −s)
!)
.
µ
N
t
¶
= C
5
N
−
1
2
exp
2
½
NH
µ
t
N
¶¾
= C
5
N
−
1
2
exp
2
(
NH
Ã
N −λ
√
N
2N
!)
.
H(t, s)
¡
N
t
¢
≤ C
6
exp
2
(
s + (N −s)H
Ã
N −s −λ
√
N
2(N −s)
!
− NH
µ
1
2
−
λ
2
√
N
¶
)
.