Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
q−
F
m
2
n F
m
2
m− F
2
F
m
2
a = (a
1
, . . . , a
m
), x =
(x
1
, . . . , x
m
)
f(x) F
m
2
F
2
f : F
m
2
→ F
2
f(x)
a ∈ F
m
2
f(a) ∈ F
2
2
m
F
m
2
2
2
m
LP
m
F
2
2
m
LP
m
LP
m
m− F
m
2
F
m
2
m− {α
0
, . . . , α
2
m
−1
} = F
m
2
{α
0
, . . . , α
2
m
−1
}
f(x)
f(x) = (f(α
0
), . . . , f(α
2
m
−1
)).
f(x) f(x
1
, . . . , x
m
)
a ∈ F
2
m
2
f(x) a = f(x)
wt(f(x)) f(x) f(x)
wt(f(x)) wt(f(x)) f(x)
1 x F
m
2
LP
m
2
m
−
LP
m
LP
m
F
m
2
j− (a
α
0
, . . . , a
α
2
m
−1
) ∈ LP
m
a
α
α = α
j
LP
m
Ω
m
ω
a
= (f
a
(α
0
), . . . , f
a
(α
2
m
−1
)), a ∈ F
m
2
,
f
a
(x) f
a
(α) = 1 a = α f
a
(α) = 0
α 6= a ω
a
a
1 0
LP
m
f(x
1
, . . . , x
m
)
f(x) ∈ F
2
[x
1
, . . . , x
m
] m F
2
f(x)
x x
x
2
= x x ∈ F
2
x
i
1
···x
i
k
f(x
1
, . . . , x
m
)
f(x
1
, . . . , x
m
) =
m
X
k=0
X
1≤i
1
<···<i
k
≤m
a
i
1
,...,i
k
x
i
1
···x
i
k
, a
i
1
,...,i
k
∈ F
2
.
F
2
mod 2
x
(a)
= x
1
(a
1
)
···x
(a
m
)
m
, x
(a)
=
(
x, a = 1 ,
x = x + 1, a = 0
,
1
x = a x
(a)
= 0 x 6= a
f(x
1
, . . . , x
m
)
f(x
1
, . . . , x
m
) =
X
f(a)=1
x
(a)
,
a ∈ F
m
2
f(a) = 1
¤
LG
m
= F
2
[x
1
, . . . , x
m
]
LG
m
x
(a)
, a ∈
F
m
2
Ω
m
LG
m
LP
m
Ξ
m
x
i
1
···x
i
k
, 1 ≤ i
1
<
··· < i
k
≤ m, k = 0, . . . , m, LG
m
Ξ
m
LG
m
|Ξ
m
| =
P
m
k=0
¡
m
k
¢
=
2
m
= dimLG
m
= dimLP
m
¤
Ξ
m
LG
m
Ω
m
LG
m
Ξ
m
Ω
m
LG
m
2
m
×2
m
− R
x
i
1
···x
i
k
R
a
i
1
,...,i
k
g(x) g(x)
g(x)
deg x
i
1
···x
i
k
x
i
1
···x
i
k
k
deg g(x) g(x)
g(x)
a
i
1
,...,i
k
F
2
m
2
r N = 2
m
r
RM
r,m
RM
r
RM
r,m
g(x) deg g(x) ≤ r
g(x) m deg g(x) ≤ r
d
RM
r,m
d k RM
r,m
d =
2
m−r
k =
¡
m
0
¢
+
¡
m
1
¢
+ ··· +
¡
m
r
¢
r
x
i
1
···x
i
k
, 0 ≤ k ≤ r
¡
m
0
¢
+
¡
m
1
¢
+ ··· +
¡
m
r
¢
wt(f(x)) f(x) ∈ RM
r
f(x) 2
m−r
m r m = 1
m
0
< m r
0
≤ r
f(x
1
, . . . , x
m
) 6= 0
f(x
1
, . . . , x
m
) = x
1
f(1, x
2
, . . . , x
m
) + (x
1
+ 1)f (0, x
2
, . . . , x
m
).
f(x) F
m
2
x
1
= 1 x
1
= 0
wt(f(x
1
, x
2
, . . . , x
m
)) = wt(f(1, x
2
, . . . , x
m
)) + wt(f(0, x
2
, . . . , x
m
)).
f(1, x
2
, . . . , x
m
) f(0, x
2
, . . . , x
m
)
wt(f(x
1
, x
2
, . . . , x
m
)) ≥ 2
m−1−r
+2
m−1−r
=
2
m−r
f(0, x
2
, . . . , x
m
) = 0 deg f(1, x
2
, . . . , x
m
) ≤
r − 1 wt(f(x)) ≥ 2
m−r
wt(f(x)) ≥ 2
m−r
f(1, x
2
, . . . , x
m
) = 0
¤
l
1
(x), . . . , l
s
(x), s ≤ m,
X
x∈F
m
2
l
1
(x) ···l
s
(x) =
0, s < m s = m l
1
(x), . . . , l
s
(x)
,
1, s = m l
1
(x), . . . , l
s
(x)
.
l
j
(x) = 1, j = 1, . . . , m,
P
x∈F
m
2
l
1
(x) ···l
s
(x) 1
s < m
X
x∈F
m
2
x
i
1
···x
i
s
=
(
0, s < m ,
1, s = m
.
P
x∈F
m
2
l
1
(x) ···l
s
(x) = 0
s = m l
j
(x) = 1, j = 1, . . . , m,
2
).,
m
(x) =
P
m−1
j=1
a
j
l
j
(x), a
j
∈ F
2
l
1
(x) ···l
m
(x) = l
1
(x) ···l
m−1
(x)
P
m−1
j=1
a
j
l
1
(x), . . . , l
m
(x) m
¤
RM
r,m
RM
m−r−1,m
x = f(x
1
, . . . , x
m
) ∈ RM
r,m
y = g(x
1
, . . . , x
m
) ∈ RM
m−r−1,m
hx, yi =
X
x∈F
m
2
f(x
1
, . . . , x
m
)g(x
1
, . . . , x
m
) = 0.
i
1
< ··· < i
s
x = f y = g deg f ≤ r
deg g ≤ n − r − 1
dim RM
r,m
+
dim RM
m−r−1,m
= N = 2
m
¤
f m
m
X
α∈F
m
2
f(α) = 0.
L = ha
1
, . . . , a
r
i r ≤ m
F
m
2
{a
1
, . . . , a
r
} α
F
m
2
L
⊥
= hb
1
, . . . , b
m−r
i
L φ
L+α
(x) L + α φ
L+α
(x)
φ
L+α
(x) =
(
1, x ∈ L + α ,
0, x 6∈ L + α
.
φ
L+0
(x) = φ
L
(x) = (b
1
(x) + 1) ···(b
m−r
(x) + 1) φ
L+α
(x) = φ
L
(x + α),
b
j
(x) = hb
j
, xi
L
⊥
L b ∈
F
m
2
ha, bi a ∈ L b
1
, . . . , b
m−r
L
⊥
b
j
(x) = 0, j = 1, . . . , m − r,
x ∈ L ¤
L
r+1
r + 1 ≤ m F
m
2
α ∈ F
m
2
X
x∈L
r+1
+α
f(x) = 0,
degf(x) ≤ r
r+1 = m
r + 1 < m
m − r − 1
X
x∈L+α
f(x) =
X
x∈F
m
2
φ
L+α
(x)f(x), deg φ
L+α
(x)f(x) < m,
¤
l
(L)
j
(x), j = 1, . . . , r,
L l
j
(x), j = 1, . . . , r,
L l
(L)
j
(x) = l
j
(x) x ∈ L
X
x∈L
l
1
(x) ···l
s
(x) =
0, l
(L)
1
(x), . . . , l
(L)
r
(x)
,
1, l
(L)
1
(x), . . . , l
(L)
r
(x)
.
¤
L r + 1 ≤ m
F
m
2
X
x∈L+α
f(x) = 0,
degf(x) ≤ r
L r ≤ m F
m
2
α ∈ F
m
2
f(x) t ≥ r
g(x) =
X
x∈L+α
f(x),
t − r
g
0
(x) =
P
x∈L+α
f
0
(x) f
0
(x) = x
i
1
···x
i
t
, i
1
< ··· < i
t
, t − r
deg
P
x∈L
0
+α
f
0
(x) ≤ t−1, L
0
¤
d
b
t
r = const m → ∞ RM
r,m
b
t =
1
2
(1 −b²
m
)2
m
O(m
r−1
2
m
) b²
m
= b²
m,r
m → ∞
b²
m
b²
m
RM
r,m
²
r,m
b
t ≈
1
2
(1 − ²
m
)2
m
r ≥ 2
RM
r,m
²
m
²
m
RM
2,m
²
m
≈ Cm2
−
m
2
O(m2
m
)
²
m
& C
0
m
1
2
2
−
m
4
C, C
0
RM
1,m
f
f
a
(x) = a
1
+ ··· + a
m
+ a
0
, a
j
∈ F
2
2 · 2
m
N = 2
m
RM
1,m
a
0
∈ F
m
2
a ∈ RM
1,m
2
m
× 2
m
−
A
m
= k(−1)
ha,bi
k, a, b ∈ F
m
2
, ha, bi = a
1
b
1
+ ··· + a
m
b
m
.
F
m
2
= {α
1
, . . . , α
N
}, N = 2
m
A
{α
1
, . . . , α
N
}
y ∈ F
2
m
2
e
y = ((−1)
y
1
, . . . , (−1)
y
N
), N = 2
m
e
yA
m
= (δ
α
1
, . . . , δ
α
N
), N = 2
m
,
δ
α
j
= N −2d(y, f
α
j
(x))
d
α
s
yA
f
α
s
(x) f
α
s
(x)
y
RM
1,m
e
y
A
m
T
m
yA
m
2
2m
= N
2
T
m
A
m
m2
m
T
m
≤ m2
m
A
m
A
m
= A
(1)
m
···A
(m)
m
A
(j)
m
yA
m
A
(j)
m
T
(1)
m
+ ···+ T
(m)
m
T
(j)
m
A
(j)
m
A
(j)
m
±1 T
(j)
m
= 2
m
T
m
≤
T
(1)
m
+ ··· + T
(m)
m
= m2
m
A
(j)
m
A = ka
i,j
k k ×k− B = kb
u,v
k s × s− ks ×ks−
A ⊗B A B
A ⊗ B = ka
i,j
Bk = kAb
u,v
k = ka
i,j
b
u,v
k, i, j = 1, . . . , k, u, v = 1, . . . , s.
A
m
A
m
= A
1
⊗ A
1
⊗ ··· ⊗ A
1
= ⊗A
m
1
,
A
1
=
µ
1 1
1 −1
¶
=
¡
(−1)
ab
¢
, a, b ∈ F
2
, 2
A
(j)
m
, j =
1, . . . , m, A
(j)
m
= I
2
j−1
⊗A
1
⊗I
2
m−j
I
2
j
2
j
A
(m−j)
m
±1
A
m
A
m
= I
2
⊗ A
m−1
· A
m−1
1
⊗ I
2
m−1
.
A
(m)
m
A
m−1
1
⊗ I
2
m−1
A
m−1
A
(m−1)
m
I
2
⊗A
1
⊗I
2
m−2
A
m
= I
4
⊗A
m−2
·I
2
⊗A
1
⊗
I
2
m−2
· A
m−1
1
⊗ I
2
m−1
A
(m−j)
m
I
2
j−1
⊗ A
1
⊗ I
2
m−j
A
(m−j)
m
±1 ¤
e
y
A
m
m2
m
R
O(m2
m
)
2
m−2
−1
RM
1,m
RM
1,m
O(2
m
)
r > 1
˜
yA
m,r
,
A
m,r
2
m
×2
dim RM
m,r
−
˜
a = ((−1)
a
1
, . . . , (−1)
a
2
m
)
T
a = (a
1
, . . . , a
2
m
) ∈ RM
m,r
˜
y 2
m
−
O(2
dim RM
m,r
)
r > 1
r−
GAm F
m
2
σ : x → xA + α, x ∈ F
m
2
,
α ∈ F
m
2
A m ×m− F
2
f(x) ∈ RM
r,m
g(x) ∈ RM
r,m
g(x) = f(xA + α)
RM
r,m
f
A,α
= f(x) + f(xA + α), x ∈ F
m
2
,
RM
r,m
f
A,α
f(x)
f
A,α
f(x)
f(xA + α) f(x)
σ
A, α f
RM
r,m
f
A,α
RM
r,m
RM
r,m
(A, α)
A
E
σ : x → x + α, α ∈ F
m
2
, F
m
2
f
E,α
= f
α
(x) = f(x) + f(x + α)