Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
d−1
X
s=1
(q − 1)
s
µ
n
0
s
¶
< q
r
− 1,
r− F
r
q
B
0
d − 1
n ¤
n → ∞
¡
n
j
¢
H
2
(x)
H
2
(x) = −x log
2
x − (1 − x) log(1 − x), 0 < x < 1.
λn
0 < λ < 1
1
p
8nλ(1 − λ)
2
nH
2
(λ)
≤
µ
n
λn
¶
≤
1
p
2 πnλ(1 −λ)
2
nH
2
(λ)
n!
√
2 πn
n+
1
2
e
−n+
1
12n
−
1
360n
3
< n! <
√
2 πn
n+
1
2
e
−n+
1
12n
µ
n
λn
¶
=
n!
λn!(n − λn)!
=
1
p
2 πnλ(1 −λ)
2
nH
2
(λ)
¤
µ
n
[λn]
¶
=
1
p
2 πnλ(1 −λ)
2
nH
2
(λ)(1+ε
n
)
, n → ∞, ε
n
→ 0.
R(n, d) =
1
n
log
2
M
2
(n, d)
n d
M(n, d) ≥ 2
log
2
M(n, d)
n
log
2
M(n,d)
n, d, w
d
n
→ δ, n → ∞,
w
n
→ ω, n → ∞, 0 < δ, ω <
1
2
,
δ ω
δ ω
R(δ) = lim
n→∞,
d
n
→δ
R(n, d),
lim
δ
R(δ) ≤ 1 − H
2
µ
δ
2
¶
R(δ) ≤ 1 − H
2
µ
1
2
−
1
2
√
1 − 2δ
¶
¤
1 − H
2
¡
δ
2
¢
0 < δ ≤
1
2
1 −H
2
¡
1
2
−
1
2
√
1 − 2δ
¢
d δ =
1
2
1 − H
2
¡
1
4
¢
d
0 < δ <
1
2
δ
R(δ) ≥ 1 − H
2
(δ)
1 − H
2
(δ) 1 −
H
2
¡
1
2
−
1
2
√
1 − 2δ
¢
(0,
1
2
) δ
q−
q > 7
R
n
n−
R λ
K ⊂ R λ(K)
K
M λ(K)
•
•
•
•
G
G
G
·
F
l
q
l− F
q
+
S C
1 S 1 C
S
G $ : G → S G
$(gh) = $(g)$(h) g, h ∈ G.
$ $
0
$(g)$
0
(g)
G
e
G G
G
e
G
h G $(g) ∈
e
G
e
G G $(g)
$
h
(g)
G %
G
e
G
$
h
(g) = $
g
(h).
%
G
G
1
, . . . , G
k
r
1
, . . . , r
k
g ∈ G g = g
1
···g
k
g
j
∈ G
j
G
j
r
j
(Z
r
j
, +) mod
r
j
G
j
= (Z
r
j
, +)
$(g) ∈
e
G $(g) = $
(1)
(g
1
) ···$
(k)
(g
k
)
$
(j)
G
j
$
(j)
G
j
$
(j)
(g
j
) = $
(j)
h
j
(g
j
) = exp
µ
2π i g
j
h
j
r
j
¶
, g
j
, h
j
∈ Z
r
j
,
h
j
∈ (Z
r
j
, +) %
% : h
1
···h
k
→ $(g) = $
(1)
(g
1
) ···$
(k)
(g
k
)
e
G G ¤
G
σ G σ G
(gh)
σ
= g
σ
h
σ
g, h ∈ G .
End(G)
End(G)
G
End(G)
G Aut(G)
Aut(G) σ
0
σ : g → h
−1
gh
G G
h σ
Inn(G)
Inn(G)
G Inn(G)
Inn(G)
G
σ : g → g
r
G
r |G| G σ
G G N
σ |Aut(G)| = ϕ(|G|) ϕ(N)
r, 1 ≤ r ≤ N, N
e
G
G
σ ∈ Aut(G).
eσ : $(g) → $(g
σ
) = $
eσ
(g),
e
G eσ
e
G σ G
H Aut(G)
e
H Aut(
e
G)
eσ σ ∈ H
H
e
H
G
• G
• G
G
e
G g $ = $
h
h G $(g) ∈
e
G
e
G G
f
1
(g) f
2
(g) G
C f
1
(g) f
2
(g)
(f
1
, f
2
) =
1
|G|
X
g∈G
f
1
(g)f
2
(g),
a, a ∈ C, a
f
D
(g) =
X
$∈D
$(g),
D
f
G
n
(f
D
, f
D
0
) = |D ∩ D
0
|.
D ∩ D
0
= ∅ f
D
, f
D
0
(f
D
, f
D
0
) = 0
$ $
0
($, $
0
) = 0 $ 6= $
0
($, $) = 1
¤
D ⊂
e
G
e
H Aut(
e
G)
H Aut(G) g ∈ G
A
g
= {g
σ
|σ ∈ H}
H
g
0
∈ A
g
A
g
A
g
A
g
0
G 1 + m
H G = ∪
m
s=0
A
g
s
g
s
, s =
0, . . . , m,
0, . . . , m A
g
s
= A
s
A
e
e G 0
G
e
G
Aut(G) Aut(
e
G)
eρ : Aut(G) → Aut(
e
G) H
e
H = eρ(H)
Aut(
e
G)
e
G 1 + m
e
A
s
=
eρ(A
w
), w ∈ {0, . . . , m},
e
H
e
A
w
, w ∈ {0, . . . , m}, $
w
e
A
w
=
e
A
$
w
$
w
e
A
w
H
Aut(G)
W (G) f(x) : G → C
W (G) C
|G| W (G)
G
$
e
G, |
e
G| = |G|,
W (G)
e
G
f(x) ∈ W (G)
f(x) =
X
$∈
f
G
l
a
$
$(x), a
$
∈ C.
$(x)
a
$
a
$
= (f(x), $(x)).
H Aut(G) f(x), f(x) ∈ W (G
n
),
H f(x) = f(x
ϕ
) ϕ ∈ H
x ∈ G
A
g
= {g
ϕ
|ϕ ∈ H}
G
n
H g ∈ G
l
A
g
= A
s
f
A
s
, s = 0, . . . , m
G = F
l
p
l− F
p
H = Aut(G)
Aut(G) F
l
p
M
l
(F
p
) l×l−
F
l
p
Aut(F
l
p
)
A
0
= {0} A
1
= F
l
p
r {0}
m = 1
F
l
p
A
0
A
1
Aut(F
l
p
)
F
∗
q
Aut(F
l
p
) F
∗
q
x → ax, a ∈ F
∗
q
x a
F
p
l
l F
p
q−1
F
∗
q
F
q
e
A
w
e
H =
f
F
l
p
e
A
0
= {1} 1 G
l
f
F
l
p
e
A
1
=
f
F
l
p
r {1}
Φ
H
(x, $)
Φ
H
(x, $) :=
X
ϕ∈H
$(x
ϕ
)
Φ
H
(x, $) = |St(x)|
X
y∈A
s
$(y), x ∈ A
s
,
St(x) x H St(x) H
x St(x) = St(y) x y
A
s
Φ
H
(x, $) x $ ∈
e
G
H
$ ∈
e
A
w
x ∈ A
s
, w, s ∈ {0, . . . , m} $
eϕ
(x) = $(x
ϕ
)
ϕ ∈ H
e
H = eρ(H)
Φ
H
(x, $)
Φ
H
(x, $) =
X
ϕ∈H
$(x
ϕ
) = |St(x)|
X
y∈A
s
$(y) =
X
eϕ∈
e
H
$
eϕ
(x) = |St($)|
X
$
0
∈
e
A
w
$
0
(x),
St(x) x H St($) $
e
H
Ψ
H
(s, $) =
P
y∈A
s
$(y)
e
A
w
$ |St(x)| A
s
x Ψ
H
(s, $) |St(x)|
P
H
(s, w) =
P
y∈A
s
$(y) S
H
(s)
Φ
H
(x, $) = S
H
(s)P
H
(s, w) =
e
S
e
H
(w)
e
P
e
H
(w, s), x ∈ A
s
, $ ∈
e
A
w
,
e
P
e
H
(w, s)
e
S
e
H
(w)
e
G
e
H
P
H
(s, w) S
H
(s)
e
P
e
H
(w, s) =
P
$∈
e
A
w
$(x) x ∈
e
A
w
e
S
e
H
(w) = |St($)|
|H| = S
H
(s)||A
s
| = |
e
S
e
H
(w)||
e
A
w
|
|
e
A
w
|P
H
(s, w) = |A
s
|
e
P
e
H
(w, s).
s
H
(x) s ∈
{0, . . . , m} x ∈ A
s
w
e
H
($) w ∈
{0, . . . , m} $ ∈
e
A
w
x ∈ G, $ ∈
e
G
Φ
H
(x, $) = S
H
(s
H
(x))P
H
(s
H
(x), w
e
H
($)) =
e
S
e
H
(w
e
H
($))
e
P
e
H
(w
e
H
($), s
H
(x)),
Y
w
(x) =
X
$∈
e
A
w
$(x)
Y
w
(x) =
e
P
e
H
(w, s
H
(x)).
w Y
w
(x)
H
A
s
e
P
e
H
(w, s), w = 0, . . . , m, |A
s
|
A
s
, s = 0, . . . , m, G
H
1
|G|
m
X
s=0
|A
s
|
e
P
e
H
(w, s)
e
P
e
H
(w
0
, s) =
(
0, w 6= w
0
|
e
A
w
|, w = w
0
,