Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
K
x ∈ F
n
q
a ∈ K
x
K
x K
≤
d(K)−1
2
x
K
x
d(x, a) ≤ t
0
a K
a
0
≤ t
0
x t
0
>
d(K)−1
2
x
x
k t
≈ 100
RS
q
(n, d)
O(n
3
) F
q
r− K [n, k, d]
r
, d ≤
n/2,
O(min(nr
k
, n
P
t
j=0
¡
n
j
¢
) t = [
d−1
2
]
r
k
K O(nr
k
)
a
0
P
t
j=0
¡
n
j
¢
(r − 1)
j
t
x O(n
P
t
j=0
¡
n
j
¢
)
BCH
r
(n, d) k
A BCH
r
(n, d)
F
r
k k × n A · C
T
= 0 C
A
C
A
r
(n, d) r−
BCH
r
(n, d) = BCH
k
(n, d) n k
d h · A · Γ · D
h k ×k F
r
D
Γ
n × n
K
r
(n, d)
A
r
(n, d) K
r
(n, d)
A
r
(n, d)
K
r
(n, d)
h, Γ, D
A
Y
X X
h = h
X
, D = D
X
, Γ = Γ
X
A
0
= A
0
X
= h
X
· A · Γ
X
· D
X
A
r
(n, d) A
0
X
h
X
, Γ
X
, D
X
X
b Y
X
n b = ~aA
0
X
+ e ~a r− k
Y e
t n Y
~a b
b = a + e,
a = ~aA
0
X
K = K
X
A
0
X
e ≤ t
K
A
0
X
A
0
X
h, D Γ
n K n
K n X
X b
~a b
0
= bD
−1
· Γ
−1
BCH
r
(n, d) A
t
D
−1
· Γ
−1
eD
−1
· Γ
−1
BCH
r
(n, d) a, a = ~a
0
A
b
0
= a + e
0
w(e
0
) ≤ t ~a ~a = ~a
0
h
−1
t ≤ (d −1)/2
t
t
RS
q
(n, d)
n ≤ q + 1
RS
q
(n, d)
RS
q
(n, d)
B
0
= h · C · D · Γ,
C h
n−k ×n−k F
r
D
Γ
n × n
X
B
0
h, D, Γ
c Y X
r n −k
c = eB
0
T
,
B
0
= B
0
X
X
B
r
(n, d) k e
n t
Y
Y e t
X e
Y
e
c = xB
0
T
.
n−k n 2
k
B
0
e
a
0
B
0
T
= eB
0
T
a
0
e a = a
0
− e
B
0
c e
B
0
A
0
B
0
· A
0
T
= 0 A
0
A
r
(n, d) B
0
N −k A
0
X c b
xB
0
T
= c b b = ~aA
0
+ e
~a ∈ F
k
r
X
bΓ
−1
· D
−1
= b
0
= ~a
0
A + e
0
~a
0
A
e
0
= b
0
−~a
0
A e = e
0
Γ · D
e
h B
0
RS
q
(n, d)
e
A
0
B
0
A
0
· B
0
T
= 0 O(n
3
)
c = eB
0
T
b = ~aA
0
+ e
~a ∈ F
k
r
c = bB
0
T
b b
Q
~a
e
e = b −~aA
0
e
~a
Q c = bB
0
T
=
(~aA
0
+ e)B
0
T
= eB
0
T
b
e ~a
~yA
0
= b − e
K
k/n
n b = ~aA
0
+ e
c = bB
0
T
= eB
0
T
e
t Y
RS
q
(n, d)
b
c
e
O((N −k)N)
e)
RS
q
(n, d)
O(n
3
)
1/2)
B
0
n − k k
A
0
B
0
B
0
· A
0
= 0
e t
r s W
t
n t s ≤ τ (t, N) = [lg
r
P
t
i=0
¡
N
i
¢
(r − 1)
i
]
B
0
A
0
c = eB
0
B
0
q
RS
q
(n, d)
A
q
(n, n − d + 1)
RS
q
(n, d)
Y
X
h, Γ, D X
X
Y X
B
0
e wt(e) ≤ t
n
n
e
B
0
A
q
(n, d)
n!(q−1)
n
(q
d−1
−1)(q
d−1
−q)···(q
d−1
−q
d−2
)
n ≈ 100 d ≤ n/2 q ≥ 2
10
77
n
h, Γ, D B
0
O(s
4
+ sn)
F
q
B
0
B
q
(n, d)
B
0
=
z
1
f
0
(ω
1
) z
2
f
0
(ω
2
) ··· z
n
f
0
(ω
n
)
z
1
f
1
(ω
1
) z
2
f
1
(ω
2
) ··· z
n
f
1
(ω
n
)
z
1
f
2
(ω
1
) z
2
f
2
(ω
2
) ··· z
n
f
2
(ω
n
)
···
z
1
f
d−2
(ω
1
) z
2
f
d−2
(ω
2
) ··· z
n
f
d−2
(ω
n
)
,
f
i
(x) ∈ F
q
[x] d − 2 d − 1 × d −
1− h = kh
i,j
k f
i
(x) =
P
d−2
j=0
h
i,j
x
j
f
i
(x) h
(ω
1
, ω
2
, . . . , ω
n
) Γ
B
0
B h ω
1
, ω
2
, . . . , ω
n
∈
F
0
q
= F
q
∪ {∞} z
1
, z
2
, . . . , z
n
∈ F
q
\ {0} B
0
= h · B · Γ · D
D = diag(z
1
, z
2
, . . . , z
n
)
ω
1
, ω
2
, . . . , ω
n
z
1
, z
2
, . . . , z
n
h
ω
j
ω
1
, ω
2
, . . . , ω
n
h, Λ B
0
= h · B · Λ, Λ = Γ · D
Λ
φ
= Γ
φ
· D
φ
, D
φ
= diag (z
0
1
, z
0
2
, . . . , z
0
n
) K
B φ(x)
h
0
, Λ
0
h
0
= h · h
00
−1
, Λ
0
= Λ
φ
· Λ h
00
h
00
· B = B · Λ
φ
Ξ
K
K = RS
q
(n, d)
x = (x
α
1
, x
α
2
, . . . , x
α
n
)
Λ
φ
φ(x)
h
0
· B · Λ
φ
· Λ =
z
00
1
f
0
0
(1) z
00
2
f
0
0
(0) z
00
3
f
0
0
(∞) ··· z
00
n
f
0
0
(β
n
)
z
00
1
f
0
1
(1) z
00
2
f
0
1
(0) z
00
3
f
0
1
(∞) ··· z
00
n
f
0
1
(β
n
)
z
00
1
f
0
2
(1) z
00
2
f
0
2
(0) z
00
3
f
0
2
(∞) ··· z
00
n
f
0
2
(β
n
)
···
z
00
1
f
0
d−2
(1) z
00
2
f
0
d−2
(0) z
00
3
f
0
d−2
(∞) ··· z
00
n
f
0
d−2
(β
n
)
,
Λ
φ
·Λ (x
ω
1
, x
ω
2
, . . . , x
ω
n
)Λ
φ
·Λ = (d
1
x
1
, d
2
x
0
, d
3
x
∞
, β
4
, . . . , β
n
)
d
ω
D
0
Λ
φ
·Λ = Λ
0
=
Γ
0
· D
0
φ(x) φ(ω
1
) =
β
1
, φ(ω
2
) = β
2
, φ(ω
3
) = β
3
β
i
Λ x
β
1
x
1
x
β
2
x
0
x
β
3
x
∞
ω
1
= 1, ω
2
= 0, ω
3
= ∞
ω
j
, j > 3
c
(1)
s
, s = 0, . . . , d − 2
z
j
d−2
X
s=0
c
(1)
s
f
s
(ω
j
) =
d−2
X
s=0
c
(1)
s
z
j
f
s
(ω
j
) = 0, j = 1, d, d + 1, . . . , 2d −4.
d − 1
c
(1)
s
kz
j
f
s
(ω
j
)k
B
0
d−2
c
(1)
s
B
0
d − 1
F
(1)
(x) =
d−2
X
s=0
c
(1)
s
f
s
(x).
γ
(1)
i
=
d−2
X
s=0
c
(1)
s
z
i
f
s
(ω
i
) = z
i
F
(1)
(ω
i
).
γ
(1)
i
z
i
f
s
(ω
i
) B
0
z
i
ω
j
, j =
1, d, d + 1, . . . , 2d − 4 F
(1)
(x)
ω
1
, ω
d
, ω
d+1
, . . . , ω
2d−4
∞ ω
3
= ∞
F
(1)
(x) d −2 f
j
(x)
d−2 F
(1)
(x)
0 f
s
(x) c
(1)
s
F
(1)
(x) = a
(1)
(x − 1)(x − ω
d
) ···(x −ω
2d−4
), a
(1)
6= 0
F
(1)
(ω) 6= 0 ω 6= ω
j
, j = 1, d, d + 1, . . . , 2d −4 ω 6= ∞ F
(1)
(∞) =
a
(1)
ω
j
, j = 2, d, d + 1, . . . , 2d − 4.
c
(2)
s
, s = 0, . . . , d − 2
d−2
X
s=0
c
(2)
s
f
s
(ω
j
) = 0, j = 2, d, d + 1, . . . , 2d −4.
F
(2)
(x) =
d−2
X
s=0
c
(2)
s
f
s
(x), γ
(2)
i
=
d−2
X
s=0
c
(2)
s
z
i
f
s
(ω
i
) = z
i
F
(2)
(ω
i
).
F
(2)
(x) = a
(2)
x(x−ω
d
) ···(x−ω
2d−4
), a
(1)
6=
0
θ(x) =
F
(1)
(x)
F
(2)
(x)
=
a
(1)
(x − 1)
a
(2)
x
F
(1)
(x) F
(2)
(x) F
(i)
(ω) 6= 0, i = 1, 2
ω 6= ω
j
, j = 1, 2, d, d + 1, . . . , 2d − 4 ω 6= ∞
θ(x) ω
j
j = d, d + 1, . . . , 2d − 4
a
(1)
a
(2)
a
(1)
a
(2)
x = ∞ ω
3
θ(x)
z
3
F
(i)
(∞) =
P
d−2
s=0
c
(i)
s
z
3
f
s
(∞), i = 1, 2 θ(∞)
B
0
z
3
f
s
(∞)
B
0
F
(i)
(∞) 6= 0
d−2 F
(i)
(x) d−2 ∞
θ(x) =
F
(1)
(∞)
F
(2)
(∞)
µ
x − 1
x
¶
F
(i)
(x) e
ω
=
θ(ω) θ(x) ω ∈ F
0
q
ω 6= ω
j
, j = 1, 2, d, d + 1, . . . , 2d −4 ω 6= ∞
ω
j
= θ
−1
(e
ω
j
), j 6= 1, 2, 3, d, d + 1, . . . , 2d −4
ω
i
, i = 1, 2, 3,
θ
−1
(x) θ
−1
(x) =
F
(1)
(∞)
F
(1)
(∞)−xF
(2)
(∞)
ω
j
j j = d, d + 1, . . . , 2d − 4
ω
j
F
(i)
(x) F
(1)
(x)
1, ω
2d−3
, ω
2d−2
, . . . , ω
3d−6
ω
j
, j =
d, d + 1, . . . , 2d −4
ω
j
j
z
i
h