Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
x e a
0
d = d(K) ≥ 2t + 1 d(K) K
d(K) < 2t + 1
e
a
0
a
0
a
a
0
a a
0
e t
(d − 1)/2
K
T (K)
q
T (n, k, t) q
O(min(nq
k
, n|V
n,t
|)) |V
n,t
|
t F
n
q
x ∈ K
wt(a
0
−x) ≤ t e
t a
0
− e ∈ K
n → ∞,
k
n
→ κ,
t
n
→ τ, 0 < κ < 1, 0 < τ <
1
2
,
T (n, k, t)
n
n O(n
3
)
q− RS
s
(A) N ≤ q
B = B
(d)
A
A = {α
1
, . . . , α
N
} ⊆ F
q
d = s + 2 ≥ 3 a ∈ F
N
q
aB
T
= 0 B
T
B
a
0
t
a ∈ RS
s
(A) e t a
0
= a + e
F
N
q
F
(t)
t F
N
q
r F
(t)
F
N
q
F
(t)
F
N
q
RS
s
(A) t
a
0
= a + e t
a
∗
RS
s
(A) a
0
= a
∗
+ e
∗
, wt(e
∗
) ≤ wt(e),
RS
s
(A) t a
∗
=
a
t a
a
0
a
∗
RS
s
(A)
a
0
wt(e)
a
0
6∈ F
(t)
a
0
t
t
a
0
K
a
0
t
t
n
b = (b
0
, . . . , b
s
) = a
0
B
T
= eB
T
=
t
X
i=1
k
j
i
B(α
j
i
), wt(e) ≤ t
k
j
i
∈ F
q
j
i
e B(α
j
) j−
B = B
(d)
A
a
0
e
b
b a
0
= a + e t
wt(e) ≤ t a
∗
∈ RS
s
(A) a
0
t RS
s
(A) t
t t
t
t e, wt(e) ≤ t,
b = eB
T
a = a
0
−e
e
x
0
= e
xB
T
= b, x ∈ F
N
q
, b ∈ F
N−k
q
,
wt(e) t
t
L(B) ⊂ F
N
q
xB
T
= 0 L(B, b)
L(B) L(B, b) = {e+y|y ∈ L(B)}
e
M(B, b)
t O(q
k
)
e t
O((q −
1)
t
¡
N
t
¢
)
k
log n
→ ∞ t → ∞
B wt(x) = u ≤ t
b
i
=
u
X
j=1
e
j
δ
i
j
, i = 0, . . . , s,
u− ∆ = {δ
1
, . . . , δ
u
} ⊂ A = {α
1
, . . . , α
N
}
E = {e
1
, . . . , e
u
},
e
u
∈ F
q
r {0}
u
b
B = {β
1
, . . . , β
u
} u− F
q
m
i
=
u
X
j=1
k
j
β
i
j
, k
j
∈ F
q
r {0}, u ≥ 1, i = 0, . . . , s, . . .
∆
r−1
=
m
0
m
1
··· m
r−1
m
1
m
2
··· m
r
···
m
r−1
m
r
··· m
2r−2
r
m
i
B
k
j
β
j
k
j
β
j
r = u ∆
r−1
6= 0
r > u ∆
r−1
= 0
u × u−
W
u−1
=
1 1 ··· 1
β
1
β
2
··· β
u
···
β
u−1
1
β
u−1
2
··· β
u−1
u
.
u− B
|W
u−1
|
∆
u−1
=
1 1 ··· 1
β
1
β
2
··· β
u
···
β
u−1
1
β
u−1
2
··· β
u−1
u
·
k
1
k
1
β
1
··· k
1
β
u−1
1
k
2
k
2
β
2
··· k
2
β
u−1
2
···
k
u
k
u
β
u
··· k
u
β
u−1
u
.
|∆
u−1
| = |W
u−1
|
2
u
Y
i=1
k
i
∆
u−1
r > u ∆
r−1
=
Q
u
i=1
k
i
W
2
r−1
W
r−1
r × r−
W
u−1
r − u > 0
W
r−1
= 0 r > u ¤
T
u
(x, y) = T
u
(x, y, B) = |∆
u−1
|
−1
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
0 1 x ··· x
u−1
1 m
0
m
1
··· m
u−1
y m
1
m
2
··· m
u
···
y
u−1
m
u−1
m
u
··· m
2u−2
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
.
x y T
u
(x, y)
T
u
(β
i
, β
j
, B) =
(
0, j 6= i ,
−
1
k
j
, j = i
.
j 1
0 1 β
i
··· β
u−1
i
1 m
0
m
1
··· m
u−1
β
1
m
1
m
2
··· m
u
···
β
u−1
1
m
u−1
m
u
··· m
2u−2
=
1 0 0 ··· 0
0 1 1 ··· 1
0 β
1
β
2
··· β
u
···
0 β
u−1
1
β
u−1
2
··· β
u−1
u
·
0 1 β
i
··· β
u−1
i
1 k
1
k
1
β
1
··· k
1
β
u−1
1
0 k
2
k
2
β
2
··· k
2
β
u−1
2
···
0 k
u
k
u
β
u
··· k
u
β
u−1
u
.
T
u
(β
i
, β
j
, B) ∆
u−1
T
u
(β
i
, β
1
, B)
W
u−1
·
c
W
u−1,i
c
W
u−1,i
0 i 6= 1
−W
u−1
Q
u
i=2
k
i
i = 1
¤
O
r
(x, m
0
, m
1
, . . . , m
2u−1
) = O
r
(x) =
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
m
0
m
1
··· m
r−1
1
m
1
m
2
··· m
r
x
m
2
m
3
··· m
r+1
x
2
···
m
r
m
r+1
··· m
2r−1
x
r
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
,
r m
i
O
u
(x, m
0
, m
1
, . . . , m
2u−1
)
u B
O
u
(x, m
0
, m
1
, . . . , m
2u−1
)
x
u
|∆
u−1
|
F
B
(x) =
u
Y
i=1
(x − β
i
) =
u
X
j=0
a
j
x
j
B
a
j
m
j
F
B
(x) O
u
(x) = |∆
u−1
|F
B
(x)
O
u
(β) = 0 β ∈ B ¤
F
B
(x)
F
B
(x) = |∆
u
|
−1
O
u
(x, b
0
, b
1
, . . . , b
2u−1
),
b = (b
0
, . . . , b
s
) = a
0
B
T
a
0
u d − 2 = s ≥ 2u − 1 u
u ≤
d−1
2
B
a
0
O
u
(x, b
0
, b
1
, . . . , b
2u−1
)
A ⊆ F
q
A
A
B
b
a
0
B O
u
(x, b
0
, b
1
, . . . , b
2u−1
)
O(u · n), n = |A|,
F
q
O
t
(x, b
0
, b
1
, . . . , b
2u−1
)
O
u
(x, b
0
, b
1
, . . . , b
2u−1
)
T
0
(u, n) F
q
O(u
4
)
a
j
x
j
∆
u,j
∆
u
∆
u,j
x
j
u ×u
O(u
3
) F
q
O
u
(x, b
0
, b
1
, . . . , b
2u−1
)
F
B
(x) A
T
1
(u, n)
F
q
un, n = |A|
T (u, n) F
B
(x)
B
T (u, n) = T
0
(u, n) + T
1
(u, n) = O(u
4
) + O(un).
n → ∞, u = const,
B O(n)
T (u, n)
a
j
F
B
(x) =
|∆
u−1
|
−1
O
u
(x, b
0
, b
1
, . . . , b
2u−1
)
m = (m
0
, m
1
, . . . , m
s
), s ≥
2u m
j
m
l+u
= −(a
u−1
m
l+u−1
+ a
u−2
m
l+u−2
+ ··· + a
0
m
l
), l ≥ 0 ,
F
B
(x) = x
u
+
P
u−1
i=1
a
i
x
i
B
m
m
1
∆
u−1
O
u
(x, m
0
, m
1
, . . . , m
2u−1
)
m s > u
u a
j
F
B
(x) =
Q
u
i=1
(x = β
i
) β
j
m
l+u
+ (x
u−1
m
l+u−1
+ x
u−2
m
l+u−2
+ ··· + x
0
m
l
= 0, l = 0, . . . , u −1,
u
m
F (x)
a
j
F (x)
m
u
u
a
j
, j = 0, . . . , u − 1.
m 2u − 1 s = 2u − 2
∆
u−1
s = 2u − 2
F
B
(x)
O(u
3
)
O(u
4
)
O
u
(x)
O(u
3
) O(u
2
)
(m
i+j
), i, j = 0, . . . , u − 1
p
O
r
(x) = O
r
(x, m
0
, m
1
, . . . , m
2r−1
), 1 ≤ r ≤ u,
2r m
j
O
0
(x) = 1
O
−1
(x) = 0
O
r
(x), r = 1, . . . , u, r
∆
r−1
, r = 2, . . . , u
B u− F
q
k
j
, j = 1, . . . , u
S
B
F
q
2u − 1
S
B
Ã
2u−1
X
i=0
a
i
x
i
!
=
2u−1
X
i=0
a
i
m
i
, a
i
∈ F
q
,
m
i
P
r
(x) =
1
p
|∆
r
| · |∆
r+1
|
O
r
(x), r = 0, . . . , u,
S
B
S
B
(P
r
(x)P
r
0
(x)) =
(
0, r 6= r
0
,
1, r = r
0
r < u
.
S
B
(x
r
O
r
0
(x)) = 0 r < r
0
r < r
0
≤ u
S
B
(x
r
O
r
0
(x)) = S
B
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
m
0
m
1
··· m
r
0
−1
x
r
m
1
m
2
··· m
r
0
x
r+1
m
2
m
3
··· m
r
0
+1
x
r+2
···
m
r
0
m
r
0
+1
··· m
2r
0
−1
x
r+r
0
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
=
=
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
m
0
m
1
··· m
r
0
−1
m
r
m
1
m
2
··· m
r
0
m
r+1
m
2
m
3
··· m
r
0
+1
m
r+2
···
m
r
0
m
r
0
+1
··· m
2r
0
−1
m
r+r
0
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
= 0,
r = r
0
< u S
B
(O
2
r
(x)) =
S
B
(|∆
r
|x
r
O
r
(x)) = |∆
r
||∆
r+1
| 6= 0 S
B
(P
2
r
(x)) =
1
|∆
r
|·|∆
r+1
|
S
B
(O
2
r
(x)) = 1 ¤
xP
r
(x) = c
r,r+1
P
r+1
(x) + c
r,r
P
r
(x) + c
r,r−1
P
r−1
(x), r = 0, . . . , u − 1
c
r,r−1
=
p
|∆
r−1
||∆
r+1
|
|∆
r
|
, c
r,r
= S
B
(x · P
2
r
(x)), c
r,r+1
=
p
|∆
r+2
||∆
r
|
|∆
r+1
|
.
xP
r
(x) r + 1
P
j
(x), j = 0, . . . , r + 1,
xP
r
(x) =
r+1
X
j=0
c
r,j
P
j
(x).
P
k
(x)
S
B
c
r,k
= 0, k = 0, . . . , r − 2,
c
r,r+1
x
r+1
¤
xP
r
(x) = a
r
P
r+1
(x) + b
r
P
r
(x) + a
r−1
P
r−1
(x),
a
r
=
p
|∆
r+2
||∆
r
|
|∆
r+1
|
, r = 0, . . . , u − 1, b
r
= c
r,r
= S
B
(x · P
2
r
(x)).
c
r,r+1
c
r,r−1
c
r,r−1
= c
r−1,r+1
P
r+1
(x)
O
r+1
(x) =
|∆
r+1
|
|∆
r
|
(b
r
− x)O
r
(x) −
s
|∆
r+1
|
3
|∆
r−2
|
|∆
r−1
|
3
|∆
r
|
O
r−1
(x).
O
r
(x), O
r−1
(x) α
r
=
|∆
r+1
|
|∆
r
|
, b
r
β
r
=
q
|∆
r+1
|
3
|∆
r−2
|
|∆
r−1
|
3
|∆
r
|
O
r
(x) O
r−1
(x)
O
r+1
(x) O(r) F
q
α
r
b
r
β
r
|∆
r+1
|
O
r
(x)
S
B
(O
2
r
(x)) = |∆
r+1
||∆
r
|.
O
r
(x) =
P
r
j=0
o
r,j
x
j
S
B
S
B
(O
2
r
(x)) = |∆
r
|S
B
(x
r
r
X
j=0
o
r,j
x
j+r
) = |∆
r
|
r
X
j=0
o
r,j
m
j+r
.
|∆
r+1
| =
r
X
j=0
o
r,j
m
j+r
.
|∆
r+1
|
o
r,j
O
r
(x) O(r) F
q