Духин А.А. Теория информации
Подождите немного. Документ загружается.
181
ЗАДАЧИ
4.
Задан источник [A,
p(s)]=[{0,l}
?
р(0) = 0,995, р(1) = 0,005]. Кодируют-
ся лишь те порождаемые источником двоичные последовательности
(e
lv
..,E
n
),
п = 100, которые содержат не более трёх единиц. В качестве
кодовых слов используются двоичные векторы (5
1
,6
2
г^5
1П
).
Определить:
a) каково должно быть m, чтобы обеспечить однозначное ко-
дирование,
b) какова вероятность порождения последовательности, кото-
рой не соответствуют кодовые слова ?
(Указание: примените распределение Пуассона, неравенство Че-
бышева)
5.
Докажите, что в
п
-мерном векторном пространстве V
n
(GF(2))
число различных базисов равно:
(2
n
-l)(2
n
-2)...(2
n
-2
n
~
l
)
6. Докажите, что число различных линейных (п,к)-кодов равно:
(2
п
-1)(2"-2М2
п
-2
ы
)
(2
к
-1)(2
к
-2)...(2
к
-2
к
~У
7.
Подсчитать вероятность ошибки декодирования при передаче
по ДСК равновероятных кодовых слов линейного кода, зада-
ваемого порождающей матрицей:
foonoi^
G = 010110
I^IOOIHJ
8. Информационные символы (б
1
,е
2
) б|=0,1 кодируются двоичным кодом
а, =(00)
а
2
=(01)
а
3
=(10)
а
4
=(П)
gi= (00000)
g
2
«
(01101)
Ss -(ЮШ)
[g
4
=(11010)J
a) Проверить, что данный код G является линейным,
b) Найти размерность кода и построить его порождающую G
и проверочную Н матрицы.
182
ГЛАВА
IV. ЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ
ОШИБКИ
с)
Определить кодовое расстояние и соответствующее ему
кодовое слово.
6) Какова корректирующая способность данного кода ?
9. Пусть алфавит А состоит из 128 символов. Предполагается, что
символы алфавита А передаются по двоичному каналу со скоростью
R=*k/n.
a) Какова должна быть длина кодового слова для передачи сим-
волов алфавита;
b) какова должна быть длина кодового слова для передачи сим-
волов алфавита при |А| = 64; 256; 64456 ?
10.
Слова двоичного кода
G
= {а
0
=(010),aj =(101)} передаются ДСК, ве-
роятность искажения в котором Р(а/<х) = р, а =
0,1.
Декодер прини-
мает решение, что передано слово а
0
, если на выходе канала появилась
последовательность из множества:
D
1
(a
o
) = {(010), (ООО), (110),
(011)},
и принимает решение, что передано слово ь
г
, в противном случае.
a) Найти вероятность принятия правильного решения.
b) Найти вероятность ошибки.
11.
Доказать, что в линейном коде над полем GF(2) либо каждый
кодовый вектор имеет чётный вес, либо половина кодовых слов
имеет чётный вес, и другая половина - нечётный. Обобщить
этот факт на случай линейных кодов над GF(q).
12.
Расположим кодовые слова линейного двоичного
(п,
к)-кода G в виде
матрицы F(2
k
х п).
a) Полагая, что в F отсутствуют нулевые столбцы, пока-
зать,
что каждый столбец содержит одинаковое число еди-
ниц и нулей.
b) Обобщить этот результат на q-чные кода над GF{q).
c) Подсчитать сумму весов всех кодовых слов. Как следствие,
получить верхнюю оценку для величины кодового расстоя-
ния линейного n, к-кода.
6) Достижима ли верхняя оценка ?
183
ЗАДАЧИ
13.
Для заданного двоичного кода:
G
= {a,=(0OO0), а
2
=(0011), а
3
=(1100), а
4
=(1Ш)}
составить таблицу декодирования по методу максимума прав-
доподобия при передаче кодовых слов по ДСК.
14.
Покажите, что метрика Хемминга удовлетворяет трём аксио-
мам:
a) аксиоме рефлективности: d(a,b) = 0
<£>
а = b,
b) аксиоме симметричности: d(a,b) = d(b,a),Va,b е V
n
,
c) неравенству треугольника: d(a,b)^ d(a,с) + d(c,b),Va,b е V
n
.
15.
Покажите, что если код 6 с минимальным расстоянием
£
+ 1
принимается в канале со стиранием, то будут исправлены все
комбинации из £ стираний, но не все комбинации из
£
+1 сти-
раний.
16.
Пусть двоичный код G используется для передачи в канале со стира-
нием.
Докажите, что для того, чтобы исправить t ошибок и £
стираний, необходимо и достаточно, чтобы минимальное ко-
довое расстояние удовлетворяло равенству d = It +
£
+1.
17.
а) Для двоичного линейного кода из задачи 8 построить таб-
лицу стандартного расположения
V
5
(GF(2)).
b) Для каждого из классов смежности вычислить синдром.
c) Декодировать вектор (11111), используя таблицу стандарт-
ного расположения и таблицу синдромов.
18.
а) Рассматривая приведённые матрицы G в качестве порож-
дающих матриц линейных кодов, указать мощность каждого
кода и его корректирующие способности:
(10011^
i)G
=
if) G
11001
ч
11100,
^10001^
11000
01100
00110
00011
184
ГЛАВА
IV.
ЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ
ОШИБКИ
iii)
G =
fnoo...ooo^
0110...000
0011...000
0000...011
jooo...ooi)
Ь)
Для
кода
с
порождающей матрицей
из
пункта
i)
построить
таблицу стандартного расположения.
19.
а)
Сколько кодовых слов содержит
код G,
задаваемый
проверочной матрицей Н
:
^0101010101^
Н
1100110111
1010001000
I,OOIIIOIIIO;
b)
Каково кодовое расстояние данного кода
?
c) Каково кодовое слово наименьшего веса
?
20.
а)
Для
кода
G,
заданного порождающей матрицей:
^101011^
6
=
011110
v
000111j
подсчитать число кодовых слов, кодовое расстояние
d,
кор-
ректирующие возможности кода
6.
b)
Построить таблицу стандартного расположения.
c)
С
использованием
ее
декодировать векторы:
f,
=(110101),
f
2
=(001111),
f
3
=(010010).
d) Найти весовой спектр кода G.
21.
ДЛЯ двоичного линейного кода
G,
задаваемого проверочной
матрицей
Н:
'000110110^
110110000
н
=
011011000
000011011
185
ЗАДАЧИ
найти образующие смежных классов, содержащих слова:
*
г
=(111101000),
а
2
= (110101011),
а
3
=(100010001),
а
4
=(010010010).
22.
Рассмотрим двоичный (п,к,с!)-код
G.
Обозначим
Go(k) -
множество
кодовых слов, которые содержат
0 на к
-й
позиции.
a) Показать,
что G
Q
(k)
есть подпространство кода G
и что
|G
0
(k)|
= l|,
V
k
=l,2,.„,n.
b) Каковы параметры кода
G
G
(k)\{o
k
} -
множества кодовых
слов,
у
которых выброшена
к -я
нулевая компонента.
c) Обобщить
эти
результаты
на
V
H
(GF(^))
?
23.
Показать,
что для
линейного (n,k,d) -кода
G
справедливы
ра-
венства:
G
0
(k)
=
|G
g
(k)|, VgeGF^),
Vk =
l,2,..,n,
G
0
(k)
=
{geG:d(g,o)
=
k},
G
g
(k)
= {reG:d(gM) =
k}.
24.
Существует
ли
совершенный (n,k
=
3)-код
при n =
147
?
25.
Доказать,
что
если
в
пространстве V
n
(GF(2)) существует
со-
вершенный
(п,к =
3)-код,
то
существует разбиение V
n+1
(GF(2))
на непересекающиеся сферы радиуса
1.
26.
Доказать,
что не
существует эквидистантных (n,2d
4-1)
кодов
мощности больше
2.
27.
Доказать,
что при
чётном
d
существует эквидистантный
код
~2п"
мощности
28.
Пусть (u
1
,u
2>
u
3
)
-
информационные символы,
м
{
=0,1. Пусть компонен-
ты
а
{
кодового слова линейного кода G задаются следующими линейны-
ми соотношениями:
186
ГЛАВА
IV.
ЛИНЕЙНЫЕ
КОДЫ,
ИСПРАВЛЯЮЩИЕ
ОШИБКИ
aj=Ui,
i =
1,2,3;
Ct
4
=
11,0112,
a
5
=u
l®
u
3>
a
6
==u
2®
u
3»
a7=U!®U2©U3,
где ® - операция сложения по модулю
2.
a) Найти параметры кода n,k,d.
b)
Построить соответствующую порождающую и проверочную
матрицы.
c) Убедиться, что заданный код систематический.
d) В предположении, что этот код используется для передачи
по ДСК с p(s/e) = p,
6
= 0,1, подсчитать вероятность оши-
бочного декодирования.
29.
Рассматривается линейный (n,k,d) код
G.
Пусть матрицы H
1
,H
2
(n-kxn) обладают свойством:
GH?
=
GH?=0.
a) Сделать вывод, что Н^Н^ - проверочные матрицы.
b)
Показать, что синдромы gilj и gttj различны.
c) Покажите, что декодирование с использованием таблиц
соответствия синдромов образующим, построенных с по-
мощью Н, и HU, приводит к одному кодовому слову g €
G
по
полученному вектору h е
V
N
(GF(#)).
30. Последовательность информационных символов
(U
1
U
2
)G
V
2
(GF(3)) ко-
дируется с использованием следующих линейных соотношений:
ai=Uj,
i = l,2;
a
3
= u, © u
2
; a
4
= u
t
© 2u
2
,
где © - сложение по модулю 3.
a) Построить порождающую G и проверочную Н матрицы для
этого кода.
b)
Составить таблицу соответствия синдромов образующим
классов смежности.
c) Предполагая, что кодовые слова передаются по троичному
симметрическому каналу, записать вероятность ошибочного
декодирования.
187
ЗАДАЧИ
31.
Двоичный код
G
задан порождающей матрицей
f1001
Г)
01010
i
,00101,
и в результате передачи по ДСК получен вектор v =
(10111).
Применяя метод последовательного декодирования, найдите
посланное кодовое слово П и покажите, что вектор u-v
имеет минимальный вес в своем классе смежности.
32.
Пусть столбцы порождающей матрицы G двоичного кода образованы из
множества столбцов V
k
\
{
0 }.
Показать, что все кодовые слова, кроме нулевого, имеют вес
2
к
~
1
.
33.
Пусть столбцы порождающей матрицы G ?-чного кода образованы из
множества столбцов V
k
\{ 0 }.
Показать, что все кодовые слова имеют одинаковый вес
34.
Укажите процедуру для исправления двух стираний для кода
Хемминга Н с кодовым расстоянием, равным 3.
35.
а) Построить двоичный код Хемминга
Н(15,11,3).
b)
Выписать порождающую и проверочную матрицы G,H.
c) Закодировать информационную последовательность
g = (11111100000).
d)
Декодировать вектор К = (111000111000111).
36.
Определение.
Код называется строго самодвойствен-
ным,
если выполнено равенство
G
=
G
1
.
Покажите, что модифицированный код Хемминга Н
п
являет-
ся строго самодвойственным.
37.
Покажите, что производящая функция для распределения ве-
сов в двоичном коде Хемминга Н
п
имеет вид:
п-1 п+1"
|(1 + х)
п
+п(1 + х)
2
(1-х)
2
f
2
00=
1
-ч
(Указание: используйте тождества Мак-Уильяме.)
188
ГЛАВА
IV. ЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ
ОШИБКИ
38.
Покажите, что для распределения весов q-чного кода
Хемминга Н
п
производящая функция имеет вид:
п(*-1)+1
1
п(?-1) + 1
n-1
[(1
+ (q-l)x)]
n
+ n(q -l)[l + (
9
-l)x]Y(1-х)
*
39.
Пусть да geV
n
W(g) = к .
Найдите |в±|, где Gg = {g' e V
n
:(g\g) = o}.
40.
Рассмотрим два линейных (n^k^d,) и (n
2
,k
2
,d
2
) кода G
1?
G
2
. Пусть
G^,Gf - коды, двойственные к заданным. Пусть код G
1
=Gjj
L
xG^ -
есть произведение двойственных кодов для заданных.
Покажите, что d
L
= min(di ^).
41.
Показать, что (G
1
)
1
= G.
42.
Найти код, двойственный к коду кратных повторений.
43.
Доказать, что если проверочная матрица Н =
(А|Е),
то код G
является строго самодвойственным, при условии, что квад-
ратная матрица А удовлетворяет соотношению
АА
Т
=
-Е.
44.
Для заданных линейных (n^k^dt) и (n
2
,k
2
,d
2
) кодов G
l5
G
2
по-
стройте код G с параметрами (п
г
+п
2
,к^ +d
2
).
45.
а) Убедиться, что каждый из кодов, заданных порождающими
матрицами G
(пример
18),
является циклическим.
Ь) Найти его порождающий многочлен, проверочный многочлен
и проверочную матрицу.
46.
Двоичный линейный (8,5)-код G задан порождающей матрицей:
fioooom^
G =
01000100
00100010
00010001
^00001111J
189
ЗАДАЧИ
a) Показать, что G - циклический код.
b) Найти его порождающий и проверочный многочлен.
c) Построить проверочную матрицу Н кода G.
d) Найти кодовое расстояние d.
47.
Циклический код G задан порождающим многочленом:
g(x) = x
8
+ x
7
+ x
6
+ x
4
+l.
a) Покажите, что длина блока п = 15.
b) Постройте порождающую матрицу G кода G.
c) Найдите проверочный многочлен h(x).
d) Построить проверочную матрицу Н кода G.
Пусть а -корень неприводимого многочлена х
4
+ х +1.
e) Покажите а,а
2
,а
3
,а
4
- корни многочлена g(x).
48.
Пусть G
l5
G
2
- циклические коды с g,(x), g
2
(x),
1ч(х),
h
2
(x) порож-
дающими и проверочными многочленами соответственно. Пусть G -
произведение этих кодов; n = njn
2
- длина блока; g(x),h(x) - порож-
дающий и проверочный многочлен. Пусть
(п
1У
п
2
)
=
1
и а и b таковы,
что an, + bn
2
= 1.
Доказать, что:
49.
Пусть многочлен g(x) порождает циклический код G над GY?{q).
Пусть длина блока п не делится на порядок поля q.
Покажите, что вектор ё = (1,1,...,1) принадлежит коду G
тогда и только тогда, когда многочлен g(x) не делится на
х-1.
50.
Пусть g(x) = g
m
x
m
+g
m
_iX
m
"
1
+... + g
0
- порождающий многочлен цик-
лического кода g(x).
Покажите, что свободный член g
0
* 0.
51.
Предложите процедуру построения циклотомических классов
по модулю 15,31,63.
52.
Постройте двоичный БЧХ-код, исправляющий две ошибки со
следующими параметрами: длина блока п = 15, число информа-
190
ГЛАВА
IV.
ЛИНЕЙНЫ,Е
коды,
ИСПРАВЛЯЮЩИЕ
ОШИБКИ
ционных символов
к = 7,
число проверочных
- n -
к
= 8.
(Указание: следует использовать
неприводимый
многочлен
h(x)
= х
4
+ х
3
4-
х
2
+
X
+1J
53.
Пусть
а,Р -
примитивные элементы поля GF(2
n
)
с
минимальными мно-
гочленами
f,(x) и
f
2
(x),
соответственно, degi
x
{x)-degi
2
{x). Пусть
a,a
2
,...,a
d_1
и (3,p
2
,...,p
d_1
-
корни кодовых слов БЧХ-кодов Gj,G
2
.
Сравните коды G
l9
G
2
.
54.
Постройте двоичный БЧХ-код, исправляющий
4
ошибки.
55.
Пусть векторы
а,Ь €
V
n
(GF(2)), d(a,b)
= d.
Пусть вектор
с €
V
n
(GF(2)) таков, что d(a,c) =
г и
d(b,c)
= s.
Показать:
а)
что число таких векторов
с
равно:
r
d\
(n-d) ^ . d
+
r-s
,
где i =
Ь)если
d
+
r-s
нечетно,
то
число таких векторов равно нулю;
с)
если г + s =
d, то
число таких векторов равно
\
г
)
56.
Найти распределение образующих классов смежности
для ко-
дов Хемминга, кодов Рида-Малера, БЧХ-кодов.
57.
Назовём
код G
максимальным, если
при
условии фиксированного рас-
стояния
d он
содержит максимальное число кодовых слов.
a) Найти максимальную мощность двоичного (п,4) кода.
b) Сколько существует максимальных двоичных (п,2) кодов
?