Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
(w, r)− K
s
= K
s
(N)
¡
n
s
¢
n s w ≤ s ≤ N −r
K
s
N =
¡
n
s
¢
T = n
K
s
(n) (w, r)− w ≤ s ≤ n − r
N(n, w, r) ≤ min
½µ
n
w
¶
,
µ
n
n − r
¶¾
,
N(n, a, w , r) ≤
µ
N
a
¶
, w ≤ a ≤ N − r.
K
s
(w, r)−
(w, r)− min
©¡
N
w
¢
,
¡
N
N−r
¢ª
q− C n (w, r)−
(w, r)− w, r ≥ 1 y
1
, . . . , y
w
∈ C x
1
, . . . , x
r
∈
C, {y
1
, . . . , y
w
} ∩ {x
1
, . . . , x
r
} = ∅,
i ∈ [n] = {1, . . . , n}
{y
1,i
, . . . , y
w,i
} ∩ {x
1,i
, . . . , x
r,i
} = ∅.
(w, r)− w r
(w, r)− (r, w)−
C = F
n
q
(1, 1)−
x, y ∈ C
(1, 2)−
C ⊂ F
n
q
n = q
m <
q
2
C q−
q m C m + 1
C (1, 2)−
x, y
1
, y
2
x
i
6∈ {y
1,i
, y
2,i
}
(y
1,i
− x
i
)(y
2,i
− x
i
) 6= 0
F (x) = (g
1
(x)−f(x))(g
2
(x)−f(x)) deg f, g
1
, g
2
<
q
2
q
x F
q
R(C) q− (w, r)− C n
R(C) =
log
q
|C|
n
.
R
q
(n, r, w) = max R(C) q−
(w, r)− n
R
q
(w, r) = lim
n→∞
R
q
(n, r, w),
q− (w, r)−
R
q
(n, r, w) q−
(w, r)− n
q, w, r = const, n → ∞
R
q
(w, r) = lim
n→∞
R
q
(n, r, w),
R
q
(w, r)
q− (w, r)−
(w, r)−
(w, r)− R
2
(w, r) Y (w, r)
Y (w, r) =
1
w + r − 1
max
0<p<1
l og
2
¡
(1 − p
w
(1 − p)
r
− p
r
(1 − p)
w
)
−1
¢
.
Y (2, 1) = 0.2075
RS
q
(n, d) F
q
n ≤ q + 1
d k = n − d + 1
RS
q
(n, d) (r, w)−
n ≥ wr(k − 1) + 1 q
k
> r + w
x R S
q
(n, d)
α
f
f(x) k−1
{α
1
, . . . , α
n
} ⊆ F
q
F
q
n = q F
q
F (x) =
w
Y
i=1
r
Y
j=1
(f
i
(x) − g
j
(x))
{α
1
, . . . , α
n
} f
i
(x)
g
j
(x) y
1
, . . . , y
w
∈ RS
q
(n, d)
x
1
, . . . , x
r
∈ RS
q
(n, d)
n ≥ wr(k − 1) + 1
deg F (x) < n
F (x) {α
1
, . . . , α
n
}
¤
RM
t,m
n = 2
m
m
d = 2
m−t
k =
P
t
j=0
¡
m
j
¢
RM
s,m
(r, w)− m ≥ srw 2
m
>
r + w
(w, 1)−
(w, 1)−
x, y ∈ F
n
q
x · y x, y
x · y = (x
1
y
1
, . . . , x
n
y
n
).
F
q
C
(w, 1)− x
1
, . . . , x
w
∈ C
x
1
···x
w
6= 0.
x
0
1
, . . . , x
0
w
, x ∈ C, x 6∈ {x
0
1
, . . . , x
0
w
}
x
i
x x
i
∈
{x
0
1,i
, . . . , x
0
w,i
}, i = 1, . . . , n x
1
= x
0
1
− x, . . . , x
w
= x
0
w
− x
C
x
i
x x
i
6∈ {x
0
1,i
, . . . , x
0
w,i
}
¤
C (2, 1)−
x, y ∈ C \ {0}
wt(x + y) < wt(x) + wt(y),
wt(x) x
x·y = (0, . . . , 0), x, y ∈ C\{0} wt(x +y) = wt(x)+
wt(y) x · y 6= (0, . . . , 0)
¤
F
q
C (2, 1)−
x ∈ C \ {0}
n
3
< wt(x) <
2n
3
.
x·y = 0 wt(x+y) = wt(x)+wt(y) >
2n
3
¤
(w, r)−
q− (w , r)− q = const, w > 1, n → ∞
q = 2
R = 1−H
2
¡
1
3
¢
= 0.0817042
(2, 1)− 0.0817042
(2, 1)−
A
n
(C)
C q− n A
(k)
= {A
(k)
1
, . . . , A
(k)
q
}, k =
1, . . . , n, q A
(k)
1
[1+( k −1)N, kN] = {1+(k −1)N, . . . , kN} A
(k)
1
A
(k
0
)
1
k 6= k
0
[1 + (k − 1)N, kN]
[1 + (k
0
−1)N, k
0
N]
A
n
(C)
A
x
= A
(1)
x
1
∪ A
(2)
x
2
∪ ··· ∪ A
(n)
x
n
, x = (x
1
, . . . , x
n
) ∈ C, |A
x
| = nq,
N
n
= ∪
n
k=1
{(k − 1) + 1, . . . , N + (k − 1)N} = {1, . . . , nN} = [nN]
C
A
n
= (A
(1)
, . . . , A
(n)
)
T A
n
(C) |C|
N
n
A
n
(C)
|N
n
| = nN
C ⊆ F
n
q
q− n A N q
F
q
C
F
q
A
A
n
(C) nN |C|
C A
n
(C) A
A
n
(C)
A
(k)
= A
(0)
+ kN A
(k)
j
∈ A
(k)
A
(0)
j
A
(0)
j
= A
j
(k − 1)N
C q− (w, r)− n
A
n
= (A
(1)
, . . . , A
(n)
) (w, r)−
N A
(s)
[N]+(s−1)N
q
A
n
(C) (w, r)− nN
|C|
τ(K) =
log
2
|K|
N
K N
K = K
1
, . . . , K
m
, . . . , (w, r)−
τ(K, r, w) = lim
j→∞
τ(K
j
).
K
(r, w)−
(w, r)− K = K
1
, . . . , K
m
, . . . ,
K
1
(w, r)−
n
1
q
1
q
1
K
m
n
m
K
m+1
(r, w)−
q
m
|C
m
| = T
m
≥ q
m
T
m
→ ∞ m → ∞ q
m
∼ T
m
m → ∞
C
m+1
A
q
m
(RS
q
m
(n
m
, d
m
))
(r, w)− C
m
q
m
− (w , r)− RS
q
m
(n
m
, d
m
) n
m
, d
m
RS
q
m
(n
m
, d
m
)
n
m
q
m
k
m
RS
q
m
(n
m
, d
m
) n
m
>
wr(k
m
−1) RS
q
m
(n
m
, d
m
) q
m
− (w, r)−
q
k
m
m
n
m
= q
m
A
q
m
(RS
q
m
(n
m
, d
m
))
(r, w)− q
m
N
m
q
k
m
m
, k
m
≤
q
m
wr
+ 1 N
m
(r, w)− C
m
wr > 1 τ(s)
q
(K, r, w)
K (r, w)−
|C
m
| ∼ q
m
τ(K
m+1
) ∼
log
2
q
m
wrN
m
∼
1
wr
τ(K
m
), m → ∞.
s
τ(K
m
) ∼
µ
1
wr
¶
s
τ(K
m−s
), s = const,
lim
m→∞
τ(K
m
) = 0 ¤
(w, r)− w = const ≥ 2, r = const ≥ 1, N → ∞,
τ(w, r) = lim
N→∞
log
2
T (N, w, r)
N
,
T (N, w, r) T N, w, r
w, r
(w, r)−
l−
A, |A| = T ≥ 2, [N]
l ≤ T A l−
A w = 1, . . . , l
r w + r ≤ T
l−
A = {{1, 2}, {1, 3}} (T = 2, N = 3)
[3] = {1, 2, 3} A
0
= {{1, 2, 4}, {1, 3, 5}, {2, 3, 6}}
(T = 3, N = 6) [6] 2−
2− A A
0
A =
1 1
1 0
0 1
A
0
=
1 1 0
1 0 1
0 1 1
1 0 0
0 1 0
0 0 1
.
l− w, 0 ≤
w ≤ l l− K
w
l−
ii.
l− A
q |A| = q A
0
2−
l− Q
q,l
q
R
(t)
q
= {{i
1
, . . . , i
t
}| 1 ≤ i
1
< ··· < i
t
≤ q}, 1 ≤ t ≤ q,
t− [q] = {1, . . . , q}
|R
(t)
q
| =
¡
q
t
¢
R
(t)
q
(s) R
(t)
q
s ∈ [q] |R
(t)
q
(s)| =
¡
q−1
t−1
¢
Q
q,l
(s) = R
(1)
q
(s) ∪ R
(2)
q
(s) ∪ ··· ∪ R
(l)
q
(s).
|Q
q,l
(s)| =
µ
q − 1
0
¶
+
µ
q − 1
1
¶
+ ··· +
µ
q − 1
l − 1
¶
= B(q, l).
Q
q,l
(s) [q]
l s ∈ [q]
N = B(q, l)
κ ∈ R
(1)
q
∪R
(2)
q
∪···∪R
(l)
q
[B(q, l)] κ n(κ) ∈ [B(q, l)]
A
s
⊂ [B(q, l)]
Q
q,l
(s) A
s
= A
(l)
s
= {n(κ)|κ ∈ Q
q,l
(s)}
l = 2 q = 3 |R
(1)
3
∪ R
(2)
3
| = 6 A
s
A
s
= {n({s, 1}), n({s, 2}), n({s, 3})}, s = 1, 2, 3, n({s, j}), s ≤ j,
{s, j} ⊂ {1, 2, 3} n({1, 2}) = 1, n ({1, 3}) = 2, n({2, 3}) =
3, n({1}) = 4, n({2}) = 5, n({3}) = 6 R
(1)
3
∪ R
(2)
3
A
1
= {1, 2, 4}, A
2
= {1, 3, 5}, A
3
= {2, 3, 6} A
0
A
s
Q
q,l
l ≤ q
Q
q,l
= {{Q
q,l
(1)}, . . . , {Q
q,l
(q)}}
A
(l)
q
= {A
(l)
1
, . . . , A
(l)
q
}.
[B(q, l)] l−
q−
Q
q,l
q−
l−
l− N = B(q, l) T = q
S = {s
1
, . . . , s
t
}, 1 ≤ t ≤ l t−
[q] S = [q] r S = {s
0
1
, . . . , s
0
q−t
} S [q] t = q S = ∅
A
(l)
s
1
∩ ··· ∩ A
(l)
s
1
6⊂ A
(l)
s
0
1
∪ ··· ∪ A
(l)
s
0
q−t
Q
q,l
(s
1
) ∩ ··· ∩ Q
q,l
(s
t
) 6⊂ Q
q,l
(s
0
1
) ∪ ··· ∪ Q
q,l
(s
0
q−t
).
{s
1
, . . . , s
t
} ⊂ Q
q,l
(s
1
) ∩ ··· ∩ Q
q,l
(s
t
),
Q
q,l
(s
j
) u− u = 1, . . . , l
s
j
∈ S
{s
1
, . . . , s
t
} t−
Q
q,l
(s
0
i
) Q
q,w
(s
0
i
) s
0
i
∈
[q] r S {s
1
, . . . , s
t
} ⊆ S
{s
1
, . . . , s
t
}
t
¤
C q− (w, r)− n
A
n
= (A
(1)
, . . . , A
(n)
)
l− T = q
A
(j)
q
A
n
(C) = {A
x
|x ∈ C} (w, r)−
r w ≤ l w ≥ q l = q −1
w ≤ l x
1
, . . . , x
w
, y
1
, . . . , y
r
∈ C
{y
1
, . . . , y
r
} ∩ {x
1
, . . . , x
w
} = ∅
A
x
1
∩ ··· ∩ A
x
w
= (A
(1)
x
1
∩ ··· ∩ A
(1)
x
w
) ∪ ··· ∪ (A
(n)
x
n
∩ ··· ∩ A
(n)
x
n
).
C (w, r)− k
{x
1,k
, . . . , x
w,k
} ∩ {y
1,k
, . . . , y
r,k
} = ∅.
w
0
r
0
{x
1,k
, . . . , x
w,k
}
{y
1,k
, . . . , y
r,k
} w
0
≤ w r r
0
≤ q − w
0
A
(k)
= {A
(k)
1
, . . . , A
(k)
q
}
l ≥ w l− l−
A
(k)
x
1,k
∩ ··· ∩ A
(k)
x
w,k
6⊂ A
(k)
y
1,k
∪ ··· ∪ A
(k)
y
r,k
.
r
0
≤ q − w
0
r
A
x
1
∩ ··· ∩ A
x
w
6⊂ A
x
1
∪ ··· ∪ A
x
r
.
w ≥ q l = q −1 {x
1,k
, . . . , x
w,k
}
q − 1
{y
1,k
, . . . , y
r,k
} q
¤
w = 2
A
(s)
(w, r)− C (w, r)−
A
(s)
w− A
n
(C) r
(w, r)−
(w, r)−
C q−
(w, r)− q > 1 A
(s)
w− q
r
C A
(s)
(w, r)−
q− (w, r)− q ≥ 2
w− q
Q
q,l
w r