Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования
Подождите немного. Документ загружается.
K
a
, a = (a
1
, . . . , a
n
) ∈ Q,
¡
n+t−2
t−1
¢
ξ
i
1
,...,i
t−1
(a) =
n
X
i=1
a
i
ξ
i
1
,...,i
t−1
,i
, 1 ≤ i
1
≤ i
2
≤ ··· ≤ i
t−1
≤ n.
ξ
i
1
,...,i
t−1
(a) = ξ
j
1
,...,j
t−1
(a) j
1
, . . . , j
t−1
i
1
, . . . , i
t−1
1 ≤ i
1
≤ i
2
≤ ··· ≤ i
t−1
≤ n
K
a
¡
n+t−2
t−1
¢
−
ξ
i
1
,...,i
t−1
(a), 1 ≤ i
1
≤ ··· ≤ i
t−1
≤ n K
a
a
k
a
1
,...,a
t
a
1
, . . . , a
t
k
a
1
,...,a
t
=
n
X
j
1
,j
2
,...,j
t−1
=1
a
1,j
1
a
2,j
2
···a
t−1,j
t−1
ξ
j
1
,...,j
t−1
(a
t
) =
n
X
j
1
,j
2
,...,j
t
=1
a
1,j
1
a
2,j
2
···a
t,j
t
ξ
j
1
,...,j
t
.
k
a
1
,...,a
t
a
t
k
a
1
,...,a
t
a
1
, . . . , a
t
ξ
j
1
,...,j
t
R
t
(Q)
J(x
1
, . . . , x
t
) =
P
n
j
1
,j
2
,...,j
t
=1
x
1,j
1
x
2,j
2
···x
t,j
t
ξ
i
1
,...,i
t
x
1
, . . . , x
t
J(x
1
, . . . , x
t
)
x
1
, . . . , x
t
x
j
J(, x
1
, . . . , ax
j
+ bx
0
j
, . . . , x
t
) = aJ(x
1
, . . . , x
j
, . . . , x
t
) + bJ(x
1
, . . . , x
0
j
, . . . , x
t
), a, b ∈ F
q
J(x
1
, . . . , x
t
)
x
1
, . . . , x
t
P = kp
i,j
k
i,j=1,...,n
x
1
= y
1
P, . . . , x
t
= y
t
P J(x
1
, . . . , x
t
)
y
1
, . . . , y
t
J(x
1
, . . . , x
t
) =
n
X
j
1
,j
2
,...,j
t
=1
y
1,j
1
y
2,j
2
···y
t,j
t
ξ
0
i
1
,...,i
t
,
ξ
0
i
1
,...,i
t
= ξ
0
j
1
,...,j
t
j
1
, . . . , j
t
i
1
, . . . , i
t
ξ
0
j
1
,...,j
t
, 1 ≤ j
1
≤ ··· ≤ j
t
≤ n
ξ
0
i
1
,...,i
t
ξ
i
1
,...,i
t
π (1, . . . , n)
π ξ
0
i
1
,...,i
t
= ξ
0
π(i
1
),...,π(i
t
)
x
k
= y
k
P x
k,s
=
P
n
j=1
y
k,j
p
j,s
x
k,s
y
k,j
s− j−
x
k
y
k
J(x
1
, . . . , x
t
) =
n
X
j
1
,j
2
,...,j
t
=1
Ã
n
X
s=1
y
1,s
p
s,j
1
!Ã
n
X
s=1
y
2,s
p
s,j
2
!
···
Ã
n
X
s=1
y
t,s
p
s,j
t
!
ξ
j
1
,...,j
t
=
n
X
s
1
,s
2
,...,s
t
=1
y
1,s
1
y
2,s
2
···y
t,s
t
n
X
j
1
,j
2
,...,j
t
=1
p
s
1
,j
1
p
s
2
,j
2
···p
s
t
,j
t
ξ
j
1
,...,j
t
.
ξ
0
s
1
,...,s
t
=
P
n
j
1
,j
2
,...,j
t
=1
p
s
1
,j
1
p
s
2
,j
2
···p
s
t
,j
t
ξ
j
1
,...,j
t
ξ
0
s
1
,...,s
t
=
n
X
j
1
,j
2
,...,j
t
=1
p
s
1
,j
1
···p
s
t
,j
t
ξ
π(j
1
),...,π(j
t
)
= ξ
0
π(s
1
),...,π(s
t
)
ξ
0
s
1
,...,s
t
¡
n+t−1
t
¢
ξ
0
s
1
,...,s
t
, 1 ≤ s
1
≤ ··· ≤ s
t
≤ n
ξ
i
1
,...,i
t
1 ≤ i
1
≤ ··· ≤ i
t
≤ n
P
¡
n+t−1
t
¢
ξ
0
s
1
,...,s
t
, 1 ≤ s
1
≤ ··· ≤ s
t
≤ n,
¡
n+t−1
t
¢
ξ
0
s
1
,...,s
t
, 1 ≤
s
1
≤ ··· ≤ s
t
≤ n, ¤
R
t
(Q) w
(t, w)− w + 1
Q F
q
a, b
1
, , . . . , b
t
∈ Q a = c
1
b
1
+
··· + c
l
b
w
, c
j
∈ F
q
K
a
= c
1
K
b
1
+ ··· + c
w
K
b
w
K
a
¡
n+t−2
t−1
¢
− ξ
i
1
,...,i
t−1
(a)
K
a
a
b
1
, . . . , b
w
k
a
1
,...,a
t
T =
{a
1
, . . . , a
t
} t a
T
w
= {b
1
, . . . , b
l
}
T = {a
1
, . . . , a
t
} ⊂
Q T
w
= {b
1
, . . . , b
w
} ⊂ Q
a
j
6∈ L(T
w
) k
a
1
,...,a
t
K
b
1
, . . . , K
b
l
k
a
1
,...,a
t
= hz
1
, K
b
1
i + ··· + hz
l
, K
b
l
i,
hz, K
b
i F
q
¡
n+t−2
t−1
¢
− z ∈ F
(
n+t−2
t−1
)
q
¡
n+t−2
t−1
¢
− K
b
a, b
1
, . . . , b
w
F
n
q
ω = {ω
1
, . . . , ω
n
}
a, b
1
, . . . , b
w
a = e
w+1
, b
1
= e
1
, . . . , b
w
= e
w
e
j
= (0, . . . , 0
| {z }
j−1
, 1, 0, . . . , 0
| {z }
n−j
),
j = 0, . . . , n
ω F
n
q
ξ
i
1
,...,i
t−1
ξ
0
i
1
,...,i
t−1
a, b
1
, . . . , b
w
e
w+1
, e
1
, . . . , e
w
K
b
j
ξ
i
1
,...,i
t−1
(b
j
) = ξ
i
1
,...,i
t−1
,j
, 1 ≤ i
1
≤ i
2
≤ ··· ≤ i
t−1
≤ n.
ξ
i
1
,...,i
t−1
(b
j
) ∈ K
b
j
, j = 1, . . . , w,
ξ
s
1
,...,s
t−1
,s
t
∈ K
s
j
w + 1
k
a
1
,...,a
t
ξ
s
1
,...,s
t−1
,s
t
∈ K w k
a
1
,...,a
t
K
b
1
∪ K
b
2
∪ ··· ∪ K
b
w
k
a
1
,...,a
t
k
a
1
,...,a
t
a a ∈ {a
1
, . . . , a
t
}
K
ξ
s
1
,...,s
t−1
,s
t
∈ K
s
1
, . . . , s
t−1
, s
t
w
a
j
6∈ L({b
1
, . . . , b
w
}), j = 1, . . . , t a
j
a
j
= (a
j,1
, . . . , a
j,w
, a
j,w+1
, . . . , a
j,n
)
(a
j,w+1
, . . . , a
j,n
)
a
j,s
j
, s
j
> w k
a
1
,...,a
t
Q
t
j=1
a
j,s
j
ξ
s
1
,...,s
t
, s
k
> w
¤
k
a
1
,...,a
t
w−
T
w
= {b
1
, . . . , b
w
} ⊂ Q
a
j
, j = 1, . . . , t, {b
1
, . . . , b
w
}
a
j
{b
1
, . . . , b
w
} k
a
1
,...,a
t
K
b
1
∪ K
b
2
∪ ··· ∪ K
b
w
a
j
, j = 1, . . . , t,
{b
1
, . . . , b
w
} k
a
1
,...,a
t
K
b
1
∪K
b
2
∪··· ∪ K
b
w
¤
t
Q R
t,w
(Q))
Q N
w
¡
n+t−2
t−1
¢
K
a
, a ∈ Q,
n Q t
t = 2
|K
a
| = n
R
t,w
(Q) D(R
t,w
(Q)) =
k(t, w) log
2
|M| (t, w)−
k(t, w) =
¡
n+t−2
t−1
¢
log
2
|M| = u log
2
q
w N
n
D(R
t,w
(Q)) =
µ
n + t − 2
t − 1
¶
u log
2
q,
D(R
t,w
(Q))
K
a
a ∈ Q ( t, w)− R
t,w
(Q) u
q
Q
Q n
w + 1 B
C N = |Q| C d ≥ 2 + w
Q C F
q
d ≥ 2 + w (t, w)− R
t
(Q)
Q (t, w)−
d ≥ 2 + w
Q
D(R
t,w
(Q))
N = 2
n
− 1
3 B
n
B
n
n
(t, 1)− S
B
n
N = 2
n
− 1
¡
n+t−2
t−1
¢
D(R
t
(Q)) =
¡
n+t−2
t−1
¢
u u
Q
N = 2
n
4 (t, 2)−
R
t
(Q)
N = 2
n
¡
n+t−1
t−1
¢
D(R
t
(Q)) = u
¡
n+t−1
t−1
¢
u
q RS
q
(q + 1, w + 2) q + 1
w + 2 t = 2
(t, w)− S
B
n
N = q + 1 n = w + 1
¡
n+t−2
t−1
¢
=
¡
w+t−1
t−1
¢
D(R
t,w
(Q)) = u
¡
w+t−1
t−1
¢
log
2
q u q−
w = 1 n = 2
¡
n+t−2
t−1
¢
=
¡
t
1
¢
= t
¡
w+t−1
t−1
¢
(t, w)−
(t, w)− B
t,w
N
q ≥ N
f
w
(x
1
, . . . , x
t
) w t F
q
f
w
(x) = f
w
(x
1
, . . . , x
t
) =
w
X
i
1
=0,...,i
t
=0
a
i
1
,...,i
t
x
i
1
1
, . . . , x
i
t
t
, a
i
1
,...,i
t
∈ F
q
.
c = (c
1
, . . . , c
t
), c
0
=
(c
0
1
, . . . , c
0
t
)
f
w
(c) f
w
(c
0
) c c
0
f
w
(x)
a
i
1
,...,i
t
= a
j
1
,...,j
t
,
i
1
, . . . , i
t
j
1
, . . . , j
t
f
w
(x)
f
w
(x) =
X
0≤i
1
≤···≤i
t
≤w
a
i
1
,...,i
t
∗
X
i
1
,...,i
t
x
i
1
1
···x
i
t
t
,
P
∗
i
1
,...,i
t
(i
1
, . . . , i
t
) σ
i
1
,...,i
t
(x) =
P
∗
i
1
,...,i
t
x
i
1
1
···x
i
t
t
σ
i
1
,...,i
t
(x) 0 ≤ i
1
≤ ··· ≤ i
t
≤ w,
¡
w+t
t
¢
t = 2 σ
i
1
,i
2
(x)
¡
w+2
2
¢
B
t,w
K
f
w
(x) K
f
w
(x)
Q F
q
Q = F
q
a ∈ F
q
g
a
(x
1
, . . . , x
t−1
) = f
w
(x
1
, . . . , x
t−1
, a) K
a
g
a
(x
1
, . . . , x
t−1
)
x
j
f
w
(x)
a g
a
j
g
a
(x
1
, . . . , x
t−1
)
a
¡
w+t−1
t−1
¢
g
a
(x
1
, . . . , x
t−1
) t − 1
w
A k
a
1
,...,a
t
T =
{a
1
, . . . , a
t
} k
a
1
,...,a
t
F
q
k
a
1
,...,a
t
= g
a
j
(a
1
, . . . , a
j−1
, a
j+1
, . . . , a
t
),
a
j
T
g
a
(x
1
, . . . , x
t−1
)
T
f
w
(x
1
, . . . , x
t−1
, x
t
) k
a
1
,...,a
t
T
t = 2 g
a
(x
1
, . . . , x
t−1
)
K
a
¡
w+1
1
¢
= w + 1
g
a
(x
1
, . . . , x
t−1
)
R
t
(Q)
n w + 1 Q Q
Q = (1, a
1
, a
2
, . . . , a
w
)
T
, a ∈ F
q
,
B
t,w
R
t,w
(Q)
(w, t)−
Q
t+w
Q t+w Q
t+w
= {c
1
, . . . , c
t+w
}
⊆ Q T (a) = {T
1
, . . . , T
l
} t− Q
t+w
a ∈ Q
t+w
l =
¡
w+t−1
t−1
¢
k
T
j
T
j
k
T
j
, j = 1, . . . , l, (t, w)
a
j
∈ F
q
P
l
j=1
a
j
k
T
j
6= 0
k
T
1
=
l
X
j=2
a
j
k
T
j
.
T
1
= {a
1
, . . . , a
t
} T
w
=
{b
1
, . . . , b
w
} T
1
T
w
= Q
t+w
r
T
1
T
1
∩ T
w
= ∅
T
w
r T
j
6= ∅, j > 1 .
k
T
j
, j > 1,
T
w
k
T
1
T
1
T
w
T
1
∩T
w
= ∅
(t, w)
(t, w)− ¤
|K
a
| K
a
(t, w) R
t
(Q)
|K
a
| ≥
µ
w + t − 1
t − 1
¶
.
K
a
K
a
¡
w+t−1
t−1
¢
T (a)
K
a
k
T
j
∈ T (a)
k
T
j
= l
j
(K
a
),
l
j
(z) |K
a
|
l
j
(z), j =
1, . . . ,
¡
w+t−1
t−1
¢
k
T
j
¤
t, w)− (t, w)−
n = w + 1 (t, w)− R
t
(Q)
n Q n = w+1
Q (t, w)− R
t
(Q)
RS
q
(q+1, w +2) q +1 w+2
w ≥ 1 r ≥ 0 T ≥ 2
w + r ≤ T A = {A
1
, . . . , A
T
} [N] = {1, . . . , N}
(w, r)−
w
\
s=1
A
i
s
*
r
[
j=1
A
k
j
, {i
1
, . . . , i
w
}, {k
1
, . . . , k
r
} ⊆ [T ]
{i
1
, . . . , i
w
}
\
{k
1
, . . . , k
r
} = ∅.
r = 0
w
\
s=1
A
i
s
6= ∅ {i
1
, . . . , i
w
} ⊆ [T ].
{i
1
, . . . , i
w
} {k
1
, . . . , k
r
}
w
r
(
w, r
)
−
(w, r)−
(w, r)− A
j
N 0, 1 j− 1
j ∈ A
j
A
j
A
j
N × T K = K(A)
A
j
, j = 1, . . . , T, (w, r) −
(w, r)−
K = K(A) (w, r)−
{i
1
, . . . , i
w
}, {k
1
, . . . , k
r
} ⊆ [T ] {i
1
, . . . , i
w
}∩{k
1
, . . . , k
r
} =
∅ K = K(A)
{i
1
, . . . , i
w
} 1
{k
1
, . . . , k
r
} 0
(w, r)−
K = K(A)
N K T
N, (w, r) T
(w, r)− N
T a
A
j
(1, w)−
(w, r)−
(w, r)−
N(T, w, r) (w, r)−
T N(T, a, w, r)
(w, r)− T
a
N(T, w, r) N(T, w, r)
[N] T
(w, r)−
N(T, a, w, r)
A
j
⊆ [N], j = 1, . . . , T, a