Файл: Кодирования.pdf

8.3.1. Эквивалентные преобразования графов
При решении графов сигналов используются эквивалентные преобразо- вания, позволяющие упростить структуру графа и уменьшить сложность рас- четов. На рис.
8.7
приведены элементарные эквивалентные схемы графов [
36
].
x
1
x
2
x
1
x
2
a b
a
+ b
≡
(а)
x
1
x
2
x
3
x
1
x
3
a b
a
· b
≡
(б)
x
1
x
2
x
3
x
4
x
1
x
2
x
4
a b
c ac bc
≡
(в)
x
1
x
2
x
3
x
4
x
1
x
3
x
4
a b
c ab ac
≡
(г)
Рис. 8.7. Элементарные эквивалентные схемы графов:
(а)
сложение;
(б)
умножение;
(в)
распределение (разложение) на множители справа;
(г)
распределение (разложение) на множители слева
Преобразования на рис.
8.7
являются обратимыми [
36
].
На рис.
8.8
приведено исключение узла в звезде. Такое преобразование в общем случае не является обратным. То есть, если задан граф в виде квадрата
(рис.
8.8(б)
), то не следует ожидать, что эквивалентный ему граф будет иметь форму звезды (рис.
8.8(а)
) [
36
].
x
1
x
2
x
3
x
4
x
5
a b
c d
≡
(а)
x
1
x
2
x
3
x
4
ca ba bd cd
(б)
Рис. 8.8. Исключение узла в звезде:
(а)
исходная звезда;
(б)
итоговый квадрат
74

Если преобразуемый граф содержит любые замкнутые цепи, то при его преобразовании появляются одна или больше петель, как показано на рис.
8.9
[
36
].
x
1
x
2
x
3
a b
c
X
2
b
= (X
1
a
+ X
3
c
)b = X
3
≡
(а)
x
1
x
3
ab cb
X
1
ab
+ X
3
cb
= X
3
(б)
Рис. 8.9. Пример образования петли при разделении дуги:
(а)
исходный граф;
(б)
итоговый граф с петлей
Уравнение для узлового сигнала, приведенное на рис.
8.9(б)
можно пре- образовать к виду
X
1
ab
= X
3
(1 − cb)
⇒ X
3
=
X
1
ab
1 − cb
(8.2)
Таким образом, граф на рис.
8.9(б)
можно свести к одной дуге (x
1
x
3
) с пере- дачей, равной
X
1
ab
1−cb
8.3.2. Передача графа
Передача T графа равна сигналу, возникающему в некотором зависи- мом узле, на единицу сигнала в некотором заданном узле-источнике. Если в графе содержится только один узел-сток x k
, т. е. узел, имеющий только вхо- дящие ветви, и один узел-источник x j
только с исходящими ветвями, то пере- дача графа определяется однозначно по формуле [
36
]
T
=
X
k
X
j
(8.3)
Отметим, что индексы у передачи графа в этом случае не указываются.
Если же в графе есть источник, но нет стока или стоков несколько, а также в случае произвольной структуры графа при отсутствии источников и стоков, необходимо указывать между какими узлами считается передача гра- фа. В этом случае она обозначается как T
jk
— передача графа между узлами x
j и x k
[
36
].
При определении передачи графа используются его топологические свойства. Важными топологическими параметрами графа являются его пути и контуры [
36
].
Путь — это непрерывная последовательность дуг (в указанном направ- лении), вдоль которой каждый узел встречается не более одного раза. Произ- ведение передач дуг вдоль этого пути образует передачу пути P [
36
].
75

Контур (или контур обратной связи) — это простой замкнутый путь,
вдоль которого каждый узел встречается не более одного раза за один об- ход контура. Передача контура L равна произведению передач ветвей в этом контуре [
36
].
Для примера рассмотрим граф на рис.
8.6
. Он содержит четыре раз- личных пути от узла x
1
до узла x
4
: P
1
= t
13
t
34
, P
2
= t
13
t
32
t
24
, P
3
= t
12
t
23
t
34
и P
4
= t
12
t
24
. Также в нем присутствует 3 контура: L
1
= t
23
t
32
, L
2
= t
24
t
42
и
L
3
= t
23
t
34
t
42
Зная все пути между узлами x j
и x k
и все контуры в графе можно пол- ностью выразить передачу графа T
jk
[
36
].
Для расчета передачи любого графа T
jk через p путей и m контуров ис- пользуется общее правило (
8.4
), которое часто называют формулой Мэзона–
Циммермана [
36
,
37
,
38
].
T
jk
=
[(P
1
+ P
2
+ . . . + P
p
)(1 − L
1
)(1 − L
2
) . . . (1 − L
m
)]
∗
[(1 − L
1
)(1 − L
2
) . . . (1 − L
m
)]
∗
(8.4)
Звездочка означает, что при умножении коэффициентов внутри скобок при- равнивается к нулю любой член, который содержит произведение передач двух контуров или произведение передач пути и контура, которые касаются друг друга в графе [
36
].
Формулу (
8.4
) можно переписать в виде
T
jk
=

∑
i
P
i
∏
v
(1 − L
v
)

∗

m
∏
w
=1
(1 − L
w
)

∗
=

∑
i
P
i
∏
v
(1 − L
v
)

∗
1 −
m
∑
w
=1
L
w
+

∑
s
,t
L
s
L
t

∗
−

∑
s
,t,u
L
s
L
t
L
u

∗
+ . . .
, (8.5)
где P
i
— передача i-го прямого пути (без замкнутых циклов) между узлами x j
и x k
(i = 1..p); L
v
— передача v-го контура [
38
].
В числителе формулы (
8.5
) должны находиться только те сомножите- ли (1 − L
v
), для которых контур L
v не соприкасается с путем P
i
. Звездочки в знаменателе показывают, что среди членов соответствующих сумм в произве- дениях должны отсутствовать соприкасающиеся или пересекающиеся конту- ры [
38
].
Для примера рассмотрим нахождение передачи графа для диаграммы состояний сверточного кода, которая используется для решения задачи опре- деления весового спектра сверточного кода [
37
,
38
].
На рис.
8.10
приведены диаграмма состояний сверточного кода
(рис.
8.10(а)
) и модифицированная диаграмма состояний (рис.
8.10(б)
), в ко- торой узел x
1
разделен на начальный узел x
1
и конечный узел x
0 1
. При этом
76

рассматриваются только те пути, которые выходят из узла x
1
и в него же воз- вращаются, не попадая в это состояние в промежуточные моменты — именно поэтому на модифицированной диаграмме (рис.
8.10(б)
) отсутствует петля t
11
[
37
,
38
].
x
1
x
2
x
3
x
4
t
12
t
31
t
24
t
43
t
32
t
23
t
11
t
44
(а)
x
1
x
2
x
3
x
0 1
x
4
t
12
t
23
t
31
t
24
t
43
t
32
t
44
(б)
Рис. 8.10. Диаграмма состояний сверточного кода:
(а)
исходная;
(б)
модифицированная
Модифицированная диаграмма на рис.
8.10(б)
содержит два пути между узлами x
1
и x
0 1
P
1
= (x
1
x
2
x
3
x
0 1
) = t
12
t
23
t
31
;
P
2
= (x
1
x
2
x
4
x
3
x
0 1
) = t
12
t
24
t
43
t
31
Также она содержит три контура
L
1
= (x
4
x
4
) = t
44
;
L
2
= (x
2
x
3
x
2
) = t
23
t
32
;
L
3
= (x
2
x
4
x
3
x
2
) = t
24
t
43
t
32
Таким образом, согласно формуле (
8.5
), передача графа для диаграммы на рис.
8.10(б)
между узлами x
1
и x
0 1
равна
T
11 0
=
P
1
(1 − L
1
) + P
2 1 − (L
1
+ L
2
+ L
3
) + L
1
L
2
Контрольные вопросы

9. МОДЕЛИ КАНАЛОВ ПЕРЕДАЧИ ДАННЫХ
Точное математическое описание любого реального канала передачи данных обычно весьма сложное [
13
]. Вместо этого используют упрощенные математические модели, которые позволяют выявить важнейшие закономер- ности реального канала.
В физическом канале сигнал S(t) подвергается воздействию шума n(t)
[
39
]. Схема этого явления показана на рис.
9.1
Источник сигнала
Физический канал
Приёмник сигнала
S
(t)
R
(t)
n
(t)
Рис. 9.1. Структурная схема физического канала в общем виде
Для количественной оценки степени влияния шума n(t) на сигнал S(t)
обычно используют отношение сигнал-шум (SNR), определяемое как отно- шение мощности сигнала к мощности шума, как показано в формуле
SNR =
P
с
P
ш
=
A
с
A
ш

2
,
(9.1)
где P — средняя мощность, а A — среднеквадратичное значение амплитуды.
Параметры сигнала и шума измеряются в полосе пропускания системы пере- дачи данных.
Как правило отношение сигнал-шум выражается в децибелах и рассчи- тывается по формуле
SNR
dB
= 10 log
10
P
с
P
ш

= 20 log
10
A
с
A
ш

(9.2)
В цифровой связи основным критерием качества канала связи и систе- мы передачи данных является отношение сигнал-шум, нормированное на ширину полосы пропускания и битовую скорость передачи данных. Нор- мированное отношение сигнал-шум обозначается как
E
b
N
0
и рассчитывается по формуле (
9.3
). E
b
— это энергия бита, которая представляет из себя мощ- ность сигнала P
с
, умноженную на время передачи одного бита T
b
. N
0
— это спектральная плотность мощности шума, которая выражается как отношение мощности шума P
ш на ширину полосы пропускания канала W [
40
]:
E
b
N
0
=
P
с
T
b
P
ш
/W
=
P
с
/R
P
ш
/W
=
P
с
P
ш
·
W
R
= SNR ·
W
R
,
(9.3)
где R — битовая скорость передачи данных.
78

Выделяют два основных вида моделей каналов передачи данных. Не- прерывные (аналоговые) каналы и дискретные (цифровые) каналы.
Непрерывные каналы имеют непрерывный сигнал S(t) на входе и не- прерывный сигнал R(t) на выходе. Эти сигналы являются непрерывной функ- цией от времени.
Дискретные каналы имеют на входе дискретные кодовые символы x j
, а на выходе — дискретные кодовые символы y i
, в общем случае не совпадаю- щие с x i
[
41
].
Почти во всех реальных линиях связи дискретный канал содержит внут- ри себя непрерывный канал, на вход которого подаются сигналы S(t), а с выхода снимаются искаженные помехами сигналы R(t) [
41
]. Свойства этого непрерывного канала наряду с характеристиками модулятора и демодулято- ра однозначно определяют все параметры дискретного канала. Поэтому ино- гда дискретный канал называют дискретным отображением непрерывного ка- нала. Однако при математическом исследовании дискретного канала обычно отвлекаются от непрерывного канала и действующих в нем помех и опреде- ляют дискретный канал через алфавит источника {x
0
, x
1
, . . . , x q
−1
}, вероят- ности появления символов алфавита, скорость передачи символов, алфавит получателя {y
0
, y
1
, . . . , y
Q
−1
} и значения переходных вероятностей P(y i
|x j
),
где i = 0, 1, . . . , Q, j = 0, 1, . . . , q [
41
,
13
].
Переходные вероятности P(y i
|x j
) являются вероятностями того, что при отправке в канал символа x j
на выходе будет получен символ y i
Если переходные вероятности для каждой пары i, j остаются постоян- ными и не зависят от того, какие символы передавались и принимались ранее,
то дискретный канал называется постоянным или однородным. Иногда при- меняют также другие названия: канал без памяти или канал с независимыми ошибками. Если же вероятности перехода зависят от времени или от имев- ших место ранее переходов, то канал называют неоднородным или каналом с памятью [
41
].
Также выделяют дискретно-непрерывные каналы, которые имеют дис- кретный вход и непрерывный выход.
9.1. Параметры моделей каналов ПД
Одним из параметров, использующихся для оценки и сравнения мо- делей каналов ПД является вероятность безошибочного участка, опреде- ляемая, как вероятность появления последовательности m (или более) без- ошибочных бит, за которыми следует бит с ошибкой. Она обозначается как
EFR(m)
5
[
42
] либо как P(0
m
|1) [
43
].
5
От англ. Error Free Run
79

По аналогии с вероятностью безошибочного участка вводится и веро- ятность пачки ошибок, определяемая, как вероятность появления последо- вательности из m (или более) ошибок, за которыми следует безошибочный бит. Обозначается как P(1
m
|0) [
43
].
Важным параметром канала ПД является его пропускная способность,
т. е. максимальная скорость передачи информации по всем допустимым рас- пределениям вероятностей входных сигналов. Пропускная способность кана- ла обозначается как C [
41
].
С понятием пропускной способности канала связана основная теорема теории информации — теорема кодирования. Она вперные была сформули- рована К. Шенноном [
44
] и заключается в том, что сообщения всякого дис- кретного источника могут быть закодированы сигналами канала x(t) и вос- становлены по сигналам на выходе канала y(t) с вероятностью ошибки, сколь угодно близкой к нулю, если производительность источника с фиксированной скоростью (либо производительность передающего устройства для источни- ка с управляемой скоростью) H
0
(x) меньше C. Если же H
0
(x) > C, то такое кодирование невозможно [
41
].
Для источника с управляемой скоростью эта теорема формулируется иначе: сообщения источника с управляемой скоростью можно закодировать сигналами x(t) и восстановить по сигналам y(t) на выходе канала так, чтобы вероятность ошибки была сколь угодно близка к нулю, а средняя скорость передачи — сколь угодно близка к
C
H
(x)
сообщений в секунду, где H(x) — эн- тропия источника на одно сообщение, т. е. средняя собственная информация на символ источника [
41
,
45
].
9.2. Двоичный симметричный канал
Модель двоичного симметричного канала
6
(ДСК) является самой про- стой моделью дискретного канала [
39
]. Модель ДСК соответствует случаю использования двоичной модуляции в канале с аддитивным шумом (в кото- ром выходной сигнал R(t) равен сумме входного сигнала S(t) и шума n(t)) и жёсткого решения демодулятора. Таким образом, модель ДСК является дис- кретной двоичной моделью передачи информации по каналу с абсолютно бе- лым гауссовским шумом (АБГШ), описанному в п.
9.7
[
3
]. Граф, описываю- щий модель ДСК, представлен на рис.
9.2
Входом и выходом данного канала являются наборы X = {0, 1} и
Y
= {0, 1} из двух возможных двоичных символов. Также ДСК характеризу- ется набором переходных вероятностей P(Y |X ), определяющих вероятность приёма из канала символа Y при передаче символа X . Переходные вероятно-
6
В зарубежной литературе используется англоязычное наименование Binary Symmetric Channel (BSC).
80

сти для ДСК задаются выражениями [
3
,
46
]
P
(0|0) = P(1|1) = 1 − p
0
;
P
(0|1) = P(1|0) = p
0
,
(9.4)
где p
0
— вероятность битовой ошибки в канале.
0 1
0 1
1 − p
0
p
0
p
0 1 − p
0
передано принято
Рис. 9.2. Граф модели двоичного симметричного канала
Для случая использования двух противоположных сигналов s
0
(t) = −s
1
(t) вероятность битовой ошибки p
0
связана с отношением сигнал-шум выражением [
39
,
40
]
p
0
= Q
r
2 ·
E
b
N
0

,
(9.5)
где Q(x) — функция, определяемая по формуле:
Q
(x) =
1
√
2π
∞
Z
x e
−
t2 2
dt
(9.6)
Переходные вероятности в канале ДСК не зависят от того, какие симво- лы передавались и принимались ранее, и следовательно канал ДСК является каналом без памяти [
13
].
Пропускная способность канала ДСК рассчитывается как [
13
,
47
]
C
ДСК
= 1 + p
0
log
2
p
0
+ (1 − p
0
) log
2
(1 − p
0
).
(9.7)
Из формулы (
9.7
) видно, что при p
0
= 0, 5 пропускная способность ка- нала C равна нулю. Этот случай называют обрывом канала [
13
].
Канал ДСК является частным случаем дикретного канала без памяти
(ДКБП) [
39
]. Канал ДКБП имеет на входе набор {x
0
, x
1
, . . . , x q
−1
} из q сим- волов, а на выходе — набор {y
0
, y
1
, . . . , y
Q
−1
} из Q символов, и характери- зуется набором из q · Q переходных вероятностей P(y i
|x j
), где i = 0, 1, . . . , Q,
j
= 0, 1, . . . , q. Эти переходные вероятности постоянны во времени, и перехо- ды различных символов независимы.
81

9.3. Двоичный симметричный канал со стираниями
Двоичный симметричный канал со стираниями
7
(ДСКС) является важным частным случаем канала ДСК. Как и ДСК, двоичный симметричный канал со стираниями может служить упрощённой моделью передачи данных по каналу АБГШ. Граф, описывающий модель канала ДСКС, представлен на рис.
9.3
[
48
].
0 1
0 1
e
1 − p
0
− q p
0
p
0 1 − p
0
− q q
q передано принято
Рис. 9.3. Граф модели двоичного симметричного канала со стираниями
Можно видеть, что по сравнению с моделью ДСК в ДСКС добавляется третье состояние на выходе — «стирание», вероятность которого обознача- ется q. С точки зрения аналогового канала стирание происходит в случае,
когда продетектированный аналоговый сигнал V попадает в зону, в которой значения условных функций плотности распределения вероятностей f (V /0)
и f (V /1) оказываются близки к нулю, т. е., когда демодулятор не может на- дежно опознать переданный символ. Пример подобной ситуации представлен на рис.
9.4
[
48
].
f
(V /1)
f
(V /0)
0 1
e
Рис. 9.4. Пример области принятия решений о стирании
7
В зарубежной литературе используется англоязычное наименование Binary Erasure Channel (BEC).
82