Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
H
2
³
1
2
−
p
δ(1 −δ)
´
< 1 − H
2
³
1
2
−
1
2
√
2δ
´
δ ∈ (0,
1
2
)
(0,
1
2
)
(δ
0
,
1
2
), 0 < δ
0
<
1
2
δ
(0,
1
2
)
δ
δ
d
K F
q
d B
d − 1
B d − 1
B = B
(d)
A
=
α
0
1
α
0
2
··· α
0
n
α
1
α
2
··· α
n
α
2
1
α
2
2
··· α
2
n
···
α
d−2
1
α
d−2
2
··· α
d−2
n
, d > 2,
n ≤ q A = {α
1
, α
1
, . . . , α
n
} F
q
α
0
= 1 α ∈ F
q
α = 0
d−1 B
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
β
0
1
β
0
2
··· β
0
d−1
β
1
β
2
··· β
d−1
β
2
1
β
2
2
··· β
2
d−1‘
···
β
d−2
1
β
d−2
2
··· β
d−2
d−1
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
, β
j
∈ {α
1
, α
2
, . . . , α
n
},
β
j
0 (β
0
1
, β
1
, . . . , β
d−2
1
)
T
, . . . ,
(β
0
d−1
, β
d−1
, . . . , β
d−2
d−1
)
T
d(K) K B
(d)
A
d d(K) = d d
d − 1− B
(d)
A
F
q
d
B
(d)
A
K(B
(d)
A
)
A 0 ∈ F
q
∞ B
A
B
A α ∈ A j− α = α
j
x = (x
α
1
, x
α
2
, . . . , x
α
n
) ∈ F
n
q
A
n = q −1, q, q + 1
A
d k = n − d + 1
B
(d)
A
F
q
d
−
1
n = q − 1 A
F
q
n = q A F
q
(α
0
j
, α
j
, . . . , α
d−2
j
)
T
α
j
= 0
(1, 0, . . . , 0)
T
n = q + 1, d > 3 A F
q
∞ A = F
q
∪{∞}
∞ a∞ =
∞, a 6= 0,
a
∞
= 0 α(∞) = (α
0
j
, α
j
, . . . , α
d−2
j
)
T
α
j
= ∞
(0, 0, . . . , 1)
T
f(x) =
P
d−2
s=0
f
s
x
s
d −2 ∞ f
d−2
f(∞) = 0 f(x) d −2
f(x) ∞ α(∞)
∞ 1, x, x
2
, . . . , x
d−2
f(∞)
B
A
x
j
, 0 ≤ j ≤ d − 2, A
0
RS
q
(n, d)
[n, n −d + 1, d]
q
q−
n − d + 1
n d
d
RS
q
(n, d)
n = q + 1
A
mod x
n
−1, n|q −1
RS
q
(n, d)
RS
q
(n, d) RS
q
(n, n−
d + 2) RS
q
(n, d) RS
q
(n, n −d + 3)
RS
q
(n, d) RS
⊥
q
(n, d)
B
A
RS
⊥
q
(n, d) RS
q
(n, n − d + 2)
RS
q
(n, n − d + 3)
X
x∈F
q
x
s
=
(
0, 0 ≤ s < q − 1
−1, s = q −1
.
B
(d)
A
B
(n−d+2)
A
A = F
q
dim RS
⊥
q
(n, d) = dim RS
q
(n, n −d + 2) = n −d + 1
RS
⊥
q
(n, d) = RS
q
(n, n − d + 2)
B
(d)
A
B
(n−d+3)
A
A = F
q
∪{∞}
¤
RS
q
(n, d)
B
(d)
A
B
(d
0
)
A
A = F
q
\{0} d
0
RS
q
(n, d)
a
f
= (f(α
1
), f(α
2
), . . . , f(α
n
)), {α
1
, . . . , α
n
} = A,
f(x) = f
0
+ f
1
x + ···+ f
k
x
k
k = n −d + 1
k = n −d + 2 f(α) = f
k
α = ∞
RS
q
(n, d)
a
f
deg f ≤ n −d
RS
q
(n, d)
a
f
deg f ≤ n −d + 1
a = (a
0
, a
1
, . . . , a
n−1
) ∈ F
n
q
a
(1)
= (a
1
, . . . , a
n−1
, a
0
)
a a j
a
(j)
= (a
(j−1)
)
(1)
a
(0)
= a
a j
a n − j
K a ∈ K
a
(1)
K
F
q
[x]/x
n
−1 mod x
n
−1
F
q
a = (a
0
, . . . , a
n−1
) ∈ F
n
q
a(x) = a
0
+a
1
x+···+a
n−1
x
n−1
∈ F
q
[x]/ mod x
n
−1 a(x)
a K ∈ F
n
q
K(x) F
q
[x]/ mod x
n
− 1
K K(x)
w(a(x)) a(x)
w(a) = w(a(x)) K K(x)
K K(x)
d(K) = d(K(x))
R
q
= R
(n)
q
= F
q
[x]/ mod x
n
− 1
I R
q
I = f(x)R
q
= hf(x)i,
f(x) x
n
− 1
f(x)
I
K n
K(x) R
(n)
q
K(x) = f(x)R
(n)
q
= hf(x)i f(x) ∈
F
q
[x] x
n
− 1
K(x) R
q
a(x) ∈ K(x) xa(x)
K(x)
xa(x) a
(1)
a a
(1)
∈ K
K K(x)
x
K(x) R
q
¤
f(x) K(x) = hf(x)i
x
n
− 1 =
s
Y
i=0
f
λ
i
i
(x),
f
i
(x) F
q
l
i
θ
i
∈
F
q
l
i
, i = 0, . . . , m,
K
f
(x) K
f
f(x) = f
λ
0
i
1
i
1
(x) ···f
λ
0
i
m
i
m
(x), λ
0
i
j
≤ λ
i
1
,
a(x) θ
i
1
, . . . , θ
i
m
λ
0
i
, i = 1, . . . , m K
f
(x) = f(x)R
(n)
q
.
x
n
− 1 τ
1
, . . . , τ
s
f(x)
B
f
K
f(x)
B
f
=
τ
0
1
τ
1
1
τ
2
1
··· τ
n−1
1
τ
0
2
τ
1
2
τ
2
2
··· τ
n−1
2
τ
0
3
τ
1
3
τ
2
3
··· τ
n−1
3
···
τ
0
s
τ
1
s
τ
2
s
··· τ
n−1
s
.
B
f
B
0
f
=
θ
0
i
1
θ
1
i
1
θ
2
i
1
··· θ
n−1
i
1
θ
0
i
2
θ
1
i
2
θ
2
i
2
··· θ
n−1
i
2
θ
0
i
3
θ
1
i
3
θ
2
i
3
··· θ
n−1
i
3
···
θ
0
i
m
θ
1
i
m
θ
2
i
m
··· θ
n−1
i
m
.
K
K(x) I R
(n)
q
I
f I = f (x)R
(n)
q
, f|x
n
− 1
I a(x) ∈ R
(n)
q
θ
i
1
, . . . , θ
i
m
f(x)
f(x) f(x)|x
n
−1 f(x)
x
n
− 1
a(τ
j
) = 0, j = 1, . . . , s, B
f
a
T
= 0
a(θ
j
) = 0, j = 1, . . . , m, a(θ
q
j
) = 0, j = 1, . . . , s.
a(θ
j
) = 0, j = 1, . . . , s, τ
j
F
q
θ
i
1
, . . . , θ
i
m
¤
n p F
q
(p, n) =
1 x
n
−1 x
n
−1
nx
n−1
x
n
− 1
hf
λ
i
i
(x)i hf
λ
i
+1
i
(x)i
R
(n)
q
RS
q
(n, d)
A RS
q
(n, d), n =
q − 1, R
(n)
q
x
n
− 1
RS
q
(n, d), n = q − 1,
n q −1
θ F
q
n, n|q−1, f
d,θ
(x) = (x−1)(x−θ) ···(x−θ
d−2
)
F
q
1, θ, . . . , θ
d−2
A = {α
1
, . . . , α
n
} B
(d)
A
A
θ
= {θ
j
|j = 0, . . . , n−1}
α
j
= θ
j−1
, j = 1, . . . , n
K(x) K(B
(d)
A
θ
)
R
(n)
q
f
d,θ
(x) a(x) ∈ R
(n)
q
a(θ
j
) = 0, j = 0, . . . , θ
d−2
a = (a
0
, . . . , a
n−1
)
a · B
(d)
A
θ
T
= 0.
a(θ
j
) = 0, j = 0, . . . , θ
d−2
K(x) f
d,θ
(x)
¤
K(B
(d)
A
θ
) ⊆ F
n
q
, n|q − 1,
¤
f(x), f(x)|x
n
− 1, deg f(x) = n −k,
K K(x)
I = hf(x)i f(x) R
(n)
q
mod x
n
− 1
g(x) =
x
n
−1
f(x)
, deg g(x) = k,
K
a(x) ∈ K(x)
a(x)g(x) = 0 mod (x
n
− 1).
a(x) f(x)
a(x)g(x) x
n
−1
R
(n)
q
g(x) =
P
k
i=0
g
k−i
x
i
, g
0
= 1,
x
j
a(x)g(x) = a
j
+ a
j−1
g
1
+ ··· + a
j−k+1
g
k−1
+ a
j−k
g
k
= 0, j = 0, . . . , n −1,
a
i
mod n.
a K
f(x)
a
j+k
= −(a
j+k−1
g
1
+ ··· + a
j−1
g
k−1
+ a
j
g
k
), j = 1, . . . , n,
(g
0
, g
1
, . . . , g
k
) g(x) =
x
n
−1
f(x)
(g
0
, g
1
, . . . , g
k
)
x
k
g(x
−1
) = g
k
x
k
+ g
k−1
x
k−1
+ ··· + g
1
x + g
0
¤
a K
k n − k
K f(x)
K
0
x
k
g(x
−1
)
g(x) K
K
0
= K
⊥
f(x)g(x) = 0 mod (x
n
−
1)
a(x) = f(x)a(x) ∈ K(x) b (x) = g(x)b(x) ∈ K
00
(x) K
00
g(x)
a(x)b(x) =
n−1
X
i=0
a
i
b
k−i
x
k
=
n−1
X
i=0
ha,
←−
b
(k)
ix
k
= 0 mod (x
n
− 1),
←−
b = (b
n
, b
n−1
, . . . , b
1
) b K
00
ha,
←−
b i = 0 a ∈ K, b ∈ K
00
←−
b
b ∈ K
00
K
0
x
k
g(x
−1
) ¤
RS
q
(n, d)
n = q, q = p
u
, u > 1, RS
q
(n, d) x
n
− 1
n = q + 1 RS
q
(n, d) x
n
−1
G
q+1
= {τ
j
|j = 0 , . . . , q}
F
∗
q
2
F
q
2
τ = θ
q−1
θ
F
∗
q
2
F
q
∪{∞} RS
q
(n, d)
R
(n)
q
RS
q
(n, d)
n = q + 1