Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
T r(x)
F
q
l F
r
q = r
l
T r(x) F
q
F
r
T r(x) = T r
q/r
(x) = x + x
r
+ x
r
2
+ ··· + x
r
l−1
.
T r(x) T r
r
(x) = T r(x)
T r(x) x ∈ F
q
F
r
T r(x)
F
r
T r(ax + by) = aT r(x) + bT r(y) a, b ∈ F
r
K ⊆ F
n
r
n n |q − 1, q = r
l
,
f(x) ∈ F
r
[x], f(x)|x
n
− 1, deg f(x) = n − k, K(x) =
f(x)R
(n)
r
mod(x
n
− 1)
θ
0
, θ
1
, . . . , θ
m
x
k
g(x
−1
) g(x) =
x
n
−1
f(x)
F
r
j
F
r
θ
j
θ
j
= θ
k
j
θ
F
q
a = (a
1
, a
1
, . . . , a
n
) ∈ K
a = (T
β
0
,...,β
m
(θ), T
β
0
,...,β
m
(θ
2
), . . . , T
β
0
,...,β
m
(θ
n
)), β
j
∈ F
r
j
,
T
β
0
,...,β
m
(x) = T r
r
0
/r
(β
0
x
k
0
) + ··· + T r
r
m
/r
(β
m
x
k
m
)
a
K
β
0
, . . . , β
m
T
j
(θ
j
) a
H
j
(x) = α
j
x
k
j
θ
j
∈ F
r
j
θ
r
j
j
= θ
j
T r
q/r
(H
j
(x))
T r(H
j
(x)) = T r
q/r
j
(α
j
)x
k
j
+ T r
q/r
j
(α
r
j
)x
k
j
r
+ ··· + T r
q/r
j
(α
r
l
j
−1
j
)x
k
j
r
l
j
−1
, x ∈ F
q
,
T r
q/r
j
(y) = y + y
r
j
+ ··· + y
r
l
j
−1
j
F
q
F
r
j
l
j
=
l
r
j
T r(H
j
(x)) = T r
r
j
/r
(T r
q/r
j
(α
j
)x
k
j
) = T r
r
j
/r
(β
j
x
k
j
) = T
j
(x
k
j
),
β
j
= T r
q/r
j
(α
j
)
β
j
6= 0 T r(H
j
(x))
q − 2 k
j
= q − 1 deg T
j
(x
k
j
) = 0
x x
q−1
= 1
T
j
(x
q−1
) = const x ∈ F
∗
q
S
j
T
j
(x
k
j
) S
j
∩S
j
0
j 6= j
0
θ
j
f(x)
r
i
k
j
6≡ k
j
0
mod (q − 1), j 6= j
0
, i = 0, . . . , l − 1
T
β
0
,...,β
m
(x) = T
β
0
,...,β
m
(x
k
0
) +
··· + T
β
0
,...,β
m
(x
k
m
) q −2 T (x)
x ∈ F
∗
q
a
a
K
a
(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
L a
deg x
k
g(x
−1
) = k L = K ¤
K ⊆ F
n
r
n n |q − 1, q = r
l
,
f(x) ∈ F
r
[x], f(x)|x
n
− 1, deg f(x) = n − k,
K(x) = f(x)R
(n)
r
mod(x
n
− 1)
K
θ
0
, θ
1
, . . . , θ
s
⊆ F
q
x
k
g(x
−1
) g(x) =
x
n
−1
f(x)
F
r
j
F
r
θ
j
θ
j
= θ
k
j
θ F
q
a = (a
1
, a
1
, . . . , a
n
) ∈ K
a = (a
0
, a
1
, . . . , a
n−1
), a
t
=
s
X
j=1
β
j
θ
t
j
, β
j
∈ F
r
j
, t = 0, . . . , n − 1.
a
K a
t
∈ F
r
t
G n
· G h
h = g
j
, 0 ≤ j < n g G
n > 2 G
mod n n−
G n
G
· H(G)
G = {g
0
, g
1
, . . . , g
n−1
} F
q
G F
q
k(a
g
0
, . . . , a
g
n−1
) :=
X
g∈G
a
g
g = a
g
0
g
0
+ a
g
1
g
1
+ ··· + a
g
n−1
g
n−1
, a
g
∈ F
q
,
+ ·
H(G) F
q
k(a
g
0
, . . . , a
g
n−1
) + k(a
0
g
0
, . . . , a
0
g
n−1
) = k(a
g
0
+ a
0
g
0
, . . . , a
g
n−1
+ a
0
g
n−1
)
k(a
g
0
, . . . , a
g
n−1
)k(a
0
g
0
, . . . , a
0
g
n−1
) =
X
g,g
0
∈G
a
g
a
g
0
gg
0
= k(b
g
0
, . . . , b
g
n−1
),
b
h
=
P
gg
0
=h
a
g
a
g
0
=
P
g∈G
a
g
a
g
−1
h
G (a
g
0
, . . . , a
g
n−1
)
(a
0
g
0
, . . . , a
0
g
n−1
)
G F
q
G = C
n
n x
k H(C
n
)
k = k(a
0
, . . . , a
n−1
) =
n−1
X
j=0
a
j
x
j
, a
j
∈ F
q
.
k(a
0
, . . . , a
n−1
)k(a
0
0
, . . . , a
0
n−1
) =
n−1
X
i,j=0
a
i
a
0
j
x
i+j
,
x
i+j
n
C
n
x
n
= 1 1
C
n
k(a
0
, . . . , a
n−1
)
k(a
0
0
, . . . , a
0
n−1
) F
q
x
i+j
n
x
n
− 1 x
i+j mod n
≡ x
i+j
mod x
n
− 1
H(C
n
) F
q
[x]/(x
n
− 1)F
q
[x] x
n
− 1
H(C
n
)
F
q
n × n−
C =
0 1 0 ··· 0
0 0 1 ··· 0
0 0 0 ··· 1
1 0 0 ··· 0
,
F
q
C
n
= I I
C
j
, j = 0, 1, . . . , n − 1
C
n
F
q
C
j
= C
j
, j = 0, 1, . . . , n − 1
C(n, F
q
) = C(F
q
) A = a
0
C
0
+
· + a
l−1
C
n−1
, γ
j
∈ F
q
C
j
, j = 0, 1, . . . , n − 1,
F
q
C(n, F
q
) H(C
n
)
H(C
n
) I
F
q
C(n, F
q
)
A C(F
q
) A
C(F
q
) F
q
× ··· × F
q
n
H(C
n
)
∼
=
C(F
q
)
H(C
n
)
F
q
[x]/(x
l
− 1)F
q
[x] C(F
q
)
H(C
n
) F
q
[x]/(x
l
−1)F
q
[x] C(F
q
)
π
π :
l−1
X
i=0
γ
i
C
i
↔
l−1
X
i=0
γ
i
x
i
, γ
i
∈ F
q
,
C(F
q
) F
q
[x]/(x
l
− 1)F
q
[x]
(n, q) = 1 x
n
− 1
x
n
− 1 =
s−1
Y
i=0
f
i
(x),
f
i
F
q
n
i
x
l
−1
f
i
f
i
S
r
= {rq
j
mod n |j = 0, . . . , n − 1 } Z
n
n
n
i
f
i
(x) S
r
f
i
(x)
x x
n
−1 =
0
r x
r
x
n
−1
x
r
, r = 0, . . . , n −1, mod (x
n
−1)
x
n
− 1 = 0 n
r x
r
f
i
(x)
f
i
(x) i x
r
f
i
(x)
x
r
f
i
(x) f
i
(x)
x
rq
F
q
f
i
(x)
x
r
→ x
rq
rq x
rq
n rq ∈ S
r
f
i
(x)
f
i
(x)
S
r
r x
r
f
i
(x) ¤
n q
mod n x
n
−1 = 0
x − 1
x
n
−1
x−1
q = 2 n = 2
l
− 1
1
2
l
−2
l
l
f(x) x
n
−1
R
f
R = F
q
[x]/(x
n
− 1)F
q
[x] R
x
n
−1
f(x)
deg f(x)
R
f
R
f
r(x)
R f(x)r(x) ≡ 0 mod (x
n
− 1)
R
f
R
g
f g
R
f·g
= R
f
⊕ R
g
,
⊕ F
q
R
f
R
g
R
f
⊕R
g
x
n
−1
f(x)g(x)
¤
f g
f(x) R
f
F
q
m
m = deg f(x) R
f
∼
=
F
q
[x]/f(x)F
q
[x]
R = F
q
[x]/(x
n
− 1)F
q
[x]
R
f
j
, j = 0, . . . , s − 1,
R = R
f
0
⊕ ··· ⊕ R
f
s−1
∼
=
F
q
n
0
⊕ ··· ⊕ F
q
n
s−1
¤
R
f
j
f(x) ∈ R
f
j
g(x) ∈ R
f
i
f(x)g(x) = 0 R i 6= j
R
f
ϕ
i
, i = 0, . . . , s−1 f(x) =
P
n−1
i=0
γ
i
x
i
∈
F
q
[x]/(x
n
− 1)F
q
[x] ϕ
i
(f(x))
ϕ
i
(f(x)) ≡ F
i
(x)
x
l
− 1
f
i
(x)
f(x) mod x
l
− 1,
F
i
(x), deg F
i
(x) < n
i
,
F
i
(x)
x
n
− 1
f
i
(x)
≡ 1 mod f
i
(x).
F
i
(x)
x
n
−1
f
i
(x)
f
i
(x)
f
i
(x)
ϕ
i
F
q
[x]/(x
n
− 1)F
q
[x]
R
f
i
F
q
n
i
n
i
= deg f
i
(x)
ϕ
i
(f(x)g(x)) = ϕ
i
(f(x))ϕ
i
(g(x)) ϕ
i
(f(x) +
g(x)) = ϕ
i
(f(x)) + ϕ
i
(g(x))
ϕ
i
F
q
[x](x
n
− 1)F
q
[x]
R
f
i
¤
ϕ
i
(F
q
[x]/(x
n
−1)F
q
[x]) F
q
[x]/(x
n
−
1)F
q
[x] ϕ
i
F
i
(x)
x
n
−1
f
i
(x)
= ϕ
i
(1)
1 F
q
[x]/(x
n
− 1)F
q
[x] = R
ϕ
i
(F
q
[x]/(x
n
− 1)F
q
[x])
ϕ
i
R R
i
F
q
n
i
F
q
n
(n, q) = 1
F
q
n
i
n
i
F
q
n
i
C(F
q
)
ϕ
i
R F
q
n
i
n
i
F
q
mod (x
n
− 1)
C(F
q
)
F
q
n
i
mod (x
n
− 1)
f
i
n
i
mod (x
n
− 1)
F
q
n
i
R
n × n−
D
i
= F
i
(C)F
0
i
(C)
F
i
(C) F
0
i
(C) =
x
n
−1
f
i
(x)
D
i
D
j
=
0 i 6= j
D
2
i
= D
i
D
i
C(F
q
)
C(F
q
)
F
q
F
q
D
i
= {aD
i
|a ∈ F
q
}
F
n
q
= F
n
q
D
0
⊕ F
n
q
D
1
⊕ ··· ⊕ F
n
q
D
s−1
bϕ : A → AD
i
, A ∈ C(F
q
), C(F
q
)
C(F
q
) C
i
(F
q
) = C(F
q
)D
i
C
i
(F
q
)
F
q
n
i
D
i
D
2
i
=
D
i
C
n
F
n
q
V
i
= F
n
q
D
i
n
i
, i = 0, . . . , s − 1 C
i
C
i
=
A
i
0
0 ··· 0
0 A
i
1
··· 0
0 0 ··· A
i
s−1
,
A
j
n
j
× n
j
− V
i
C(F
q
)
e 6= 0 K e
2
= e
K = F
q
F
∗
q
F
q
F
q
E K E
C(F
q
) (n, q) = 1
e e =
1
n
P
n−1
i=0
C
i
K
D
i
, i = 0, . . . , s − 1,
C(F
q
)
C(F
q
)
s F
q
D
i
, i =
0, . . . , s −1
F
i
(x)
x
n
−1
f
i
(x)
, i = 0, . . . , s −1
F
q
[x](x
n
− 1)F
q
[x]
F
q
[x](x
n
−1)F
q
[x]
s
F
i
(x)
x
n
−1
f
i
(x)
, i = 0, . . . , s −1
¤
mod (x
n
− 1)
K ⊆ F
n
q
F
q
n k
(n, q) = 1 R
i
F
q
n
i
n
i
F
q
n
i
K(x) = K
i
1
(x) ⊕ ··· ⊕ K
i
t
(x),
K
i
s
(x) = R
i
s
{i
1
, . . . , i
t
} ⊆ {0, 1, . . . , m−1}
K
i
s
(x)
k K(x) k =
P
t
s=1
dim K
i
s
=
P
t
s=1
n
i
s
K
i
(x) F
i
(x)
x
n
−1
f
i
(x)
, xF
i
(x)
x
n
−1
f
i
(x)
, . . . , x
n
i
F
i
(x)
x
n
−1
f
i
(x)
F
r
, r = p
l
0
, F
q
, q = r
l
r− RS
q,r
(n, d) RS−
RS
q
(n, d), n ≤ q + 1 RS
q
(n, d)
F
r
RS
q,r
(n, d)
B
(d)
A
θ
A
θ
θ ∈ F
q
n
RS
q
(n, d) r < q
BCH
q,r
(n, d), n|q −1)
BCH
q,r
(n, d) = RS
q
(n, d) ∩ F
n
r
, n|q −1.
RS
q
(n, d), n|q − 1,
BCH
q,r
(n, d)
BCH
q,r
(n, d), n = q −1,
BCH
q,r
(n, d)
F
∗
q
= F
q
\ {0} F
q
r < q BCH
q,r
(n, d)
BCH
q,r
(n, d)
τ : x → x
r
, x ∈ F
q
,
τ BCH
q,r
(n, d)
B
(d)
A
θ
BCH
q,r
(n, d)
A(BCH
q,r
(n, d)) BCH
q,r
(n, d)
σ
(1)
τ ln θ
F
q
B
(d)
A
θ
(θ
j−1
) j− B
(d)
A
θ
B
(d)
A
θ
j
θ ∈ F
q
n
a = (a
1
, . . . , a
n
) ∈ F
n
r
BCH
q,r
(n, d)
n
X
j=1
a
j
B
(d)
A
θ
(θ
j−1
) = 0.
r
Ã
n
X
j=1
a
j
B
(d)
A
θ
(θ
j−1
)
!
r
=
n
X
j=1
a
j
B
(d)
A
θ
(θ
r(j−1)
) = 0.
a
τ BCH
q,r
(n, d)
τσ
(1)
=
¡
σ
(1)
¢
r
τ = σ
(r)
τ σ
(r)
¡
σ
(1)
¢
r
r ι = τ
i
1
σ
(r
1
)
···τ
i
k
σ
(r
k
)
hτ, σ
(1)
i ι = σ
(j)
τ
i
i, j
l
0
θ
r
l
0
= θ hτ, σ
(1)
i
l
0
n θ ∈ F
q
F
q
l
0
= l ¤
l
0
< l r F
q
R
(n)
r
BCH
r,q
(n, d)
BCH
r,q
(n, d)(x) I = f(x)R
(n)
r
mod (x
n
−
1) f(x) BCH
r,q
(n, d)
f(x) BCH
r,q
(n, d) B
(d)
A
θ
F
r
θ
s
, s = 0, 1, . . . , d −2
m = d − 2 −
£
d−2
r
¤
{s
1
, . . . , s
m
} {1, . . . , d −
2} r f(x)
f(x) = f
0
(x)f
1
(x) ···f
m
(x),