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

Матрица переходных вероятностей канала ДСКС равна [
48
]
P
ДСКС
=
1 − p
0
− q q p
0
p
0
q
1 − p
0
− q

(9.8)
Пропускная способность канала ДСКС рассчитывается по формуле
(
9.9
) и зависит только от вероятностей p
0
и q, т. е., является функцией
C
ДСКС
= f (p
0
, q) [
48
]:
C
ДСКС
= 1 − q + (1 − p
0
− q) log
2 1 − p
0
− q
1 − q
+ p
0
log
2
p
0 1 − q
(9.9)
Важным частным случаем канала ДСКС является канал, содержащий только стирания. В таком канале p
0
= 0 — т. е. ошибок либо нет, либо мы ими пренебрегаем. На практике такой канал реализуется оптимальным под- бором области стирания, показанной на рис.
9.4
. Этот вариант канала ДСКС
интересен тем, что он позволяет достичь большей пропускной способности,
нежели обычный канал ДСК. Пропускная способность такого канала опреде- ляется формулой [
48
]
C
ДСКС
= 1 − q.
(9.10)
Граф такой модели ДСКС показан на рис.
9.5 0
1 0
1
e
1 − q
1 − q q
q передано принято
Рис. 9.5. Граф модели двоичного симметричного канала со стираниями для случая p
0
= 0 9.4. Двоичный несимметричный канал (Z-канал)
Двоичный несимметричный канал, или Z-канал
8
, является каналом без памяти с двоичным входом и двоичным выходом, в котором невозможен пе- реход 0 −→ 1. Этот канал получил свое название, благодаря характерному виду своего графа (рис.
9.6
) [
49
,
46
]. Поскольку в русскоязычной литерату- ре нет устоявшегося сокращения для канала такого типа, будем использовать англоязычную аббревиатуру ZC.
8
В зарубежной литературе используется англоязычное наименование Z-Channel (ZC).
83

0 1
0 1
1
p
1 − p передано принято
Рис. 9.6. Граф модели двоичного несимметричного канала (Z-канала)
Переходные вероятности для Z-канала задаются выражениями [
46
]
P
(0|0) = 1; P(0|1) = p;
P
(1|0) = 0; P(1|1) = 1 − p;
(9.11)
где p — вероятность ошибки в Z-канале.
Пропускная способность Z-канала рассчитывается по формуле [
49
]
C
ZC
= log
2
(1 + (1 − p)p p
1−p
).
(9.12)
Модель Z-канала используется при рассмотрении оптической и засек- реченной связи [
50
].
9.5. Канал Гилберта–Эллиотта
Канал Гилберта–Эллиотта
9
(GEC) относится к дискретным каналам с памятью, в которых состояние канала зависит от предыдущего состояния
[
49
,
51
]. Эта модель предложена в 1963 г. Эллиоттом [
52
] и является общим случаем модели Гилберта, представленной в 1960 г. [
53
].
Канал GEC представляет из себя цепь Маркова первого порядка с дву- мя состояниями — «хорошим» и «плохим», как показано на рис.
9.7
Каждое из состояний канала можно описать как канал ДСК с соответ- ствующей вероятностью ошибки [
49
,
54
]. В «хорошем» состоянии вероят- ность битовой ошибки в канале равна p
G
, в «плохом» состоянии — p
B
. В лю- бой момент времени канал может перейти из одного состояния в другое. При этом вероятности перехода могут быть отличны друг от друга. Вероятность перехода из «хорошего» состояния в «плохое» обозначим как P
GB
, а вероят- ность перехода из «плохого» состояния в «хорошее» обозначим как P
BG
, что отображено на рис.
9.7
. Соответствующая этим вероятностям матрица пере- ходов A имеет вид [
49
]
A
=
1 − P
GB
P
GB
P
BG
1 − P
BG

(9.13)
9
В зарубежной и переводной литературе используется англоязычное наименование Gilbert–Elliott Channel
(GEC).
84

0 1
0 1
1 − p
G
p
G
p
G
1 − p
G
0 1
0 1
1 − p
B
p
B
p
B
1 − p
B
G
B
1 − P
GB
1 − P
BG
P
GB
P
BG
Рис. 9.7. Канал Гилберта–Эллиотта
Из рис.
9.7
следует, что финальные вероятности пребывания канала в состояниях G и B будут определяться выражениями [
51
]:
π
G
=
P
BG
P
GB
+ P
BG
,
π
B
=
P
GB
P
GB
+ P
BG
(9.14)
Из формул (
9.14
) следует, что средняя вероятность битовой ошибки в канале может быть вычислена по формуле p
e
= p
G
· π
G
+ p
B
· π
B
(9.15)
Вероятность того, что в блоке длиной n возникнет m ошибок рассчиты- вается по формуле
P
(m, n) = π
G
· G(m, n) + π
B
· B(m, n),
(9.16)
где G(m, n) — вероятность появления m ошибок в блоке длиной n, при усло- вии, что канал во время передачи первого бита находился в состоянии G;
B
(m, n) — вероятность появления m ошибок в блоке длиной n, при условии,
что канал во время передачи первого бита находился в состоянии B.
Для расчета этих вероятностей Эллиоттом были введены рекуррентные соотношения (
9.17
), описывающие процесс возникновения ошибок в канале,
учитывая, что канал с каждым поступившим новым разрядом может оста- ваться в прежнем состоянии или переходить в другое [
52
]:
85

G
(m, n) = G(m, n − 1) · (1 − P
GB
) · (1 − p
G
)+
+B(m, n − 1) · P
BG
· (1 − p
G
)+
+G(m − 1, n − 1) · (1 − P
GB
) · p
G
+
+B(m − 1, n − 1) · P
BG
· p
G
,
B
(m, n) = G(m, n − 1) · P
GB
· (1 − p
B
)+
+B(m, n − 1) · (1 − P
BG
) · (1 − p
B
)+
+G(m − 1, n − 1) · P
GB
· p
B
+
+B(m − 1, n − 1) · (1 − P
BG
) · p
B
(9.17)
В формулах (
9.18
) приведены очевидные начальные значения вероятно- стей (
9.17
) при n = 1 [
52
]:
G
(0, 1) = (1 − p
G
), B(0, 1) = (1 − p
B
),
G
(1, 1) = p
G
,
B
(1, 1) = p
B
(9.18)
Также необходимо учитывать, что:
G
(m, n) = B(m, n) = 0,
при m < 0 или m > n.
Вероятность безошибочного участка (в случае стационарности) для ка- нала GEC рассчитывается по формуле [
42
]:
EFR
GEC
(m) = π
G
p
G
(1 − p
G
)
m
+ π
B
p
B
(1 − p
B
)
m
(9.19)
Канал GEC широко используется для описания источников ошибок в системах передачи данных, а также при анализе эффективности алгоритмов декодирования помехоустойчивых кодов [
51
].
Существуют исследования, показывающие, что канал GEC близок по своим свойствам к преобразованному в двоичную форму (квантованному)
двухлучевому Релеевскому каналу с замираниями без поворота фазы [
42
].
Часто при использовании модели GEC для двоичного канала полагают,
что вероятность p
B
= 0, 5, т. е. «плохое» состояние рассматривается как пол- ный обрыв связи [
13
]. Это согласуется с представлением о канале, в котором действуют коммутативные помехи.
9.6. Модель канала Поля
В начале 90-х гг. XX века было определено, что для описания распре- деления ошибок в коммуникационном канале с памятью может быть исполь- зована модель Г. Поля, используемая для моделирования распространения заболеваний [
55
].
86

Канал Поля является дискретным двоичным аддитивным каналом свя- зи, в котором сигнал на выходе y i
∈ {0, 1} равен сумме по модулю 2 соответ- ствующих ему сигнала на входе x i
∈ {0, 1} и бита ошибки z i
∈ {0, 1}: y i
= x i
⊕z i
,
для i = 1, 2, 3, . . . [
55
].
Принцип работы канала Поля заключается в следующем. Имеется урна,
в которой изначально содержится T шаров, из которых R красных и S черных
(T = R + S), при этом ρ = R/T и σ = 1 − ρ = S/T . На каждом шаге i из урны вытаскивается случайный шар, так что
Z
i
=
1, вытащен красный шар;
0, вытащен черный шар.
(9.20)
После этого в урну возвращается 1 + ∆ того же цвета, что и вытащенный. ∆ —
параметр модели канала (целое число). Как правило, предполагают, что ∆ > 0
и ρ < σ . Дополнительно вводится параметр δ = ∆/T [
55
].
Состоянием канала Поля после n шагов, является количество красных шаров, вытащенных за это время:
S
n
, Z
1
+ Z
2
+ . . . + Z
n
= S
n
−1
+ Z
n
(9.21)
Соответственно, начальное состояние канала: S
0
= 0 [
55
].
Таким образом, состояние канала на шаге n может принимать n + 1 зна- чение: {0, 1, . . . , n}, а последовательность состояний {S
n
}
∞
n
=1
формирует мар- ковскую цепь [
55
]
P
(S
N
= s n
|S
n
−1
= s n
−1
, S
n
−2
= s n
−2
, . . . , S
1
= s
1
) = P(S
N
= s n
|S
n
−1
= s n
−1
).
Для заданного блока данных на входе X = [X
1
, X
2
, . . . , X
n
] заданного для него блока выходных данных Y = [Y
1
,Y
2
, . . . ,Y
n
] блочная переходная вероят- ность равна
P
(X = x|Y = y) =
Γ
1
δ

Γ
ρ
δ
+ d

Γ
σ
δ
+ n − d

Γ
ρ
δ

Γ
σ
δ

Γ
1
δ
+ n

,
(9.22)
где d — расстояние Хэмминга между x и y; а Γ(x) =
∞
R
0
t x
−1
e
−t dt для x > 0 —
гамма-функция [
42
,
55
].
Вероятность безошибочного участка (в случае стационарности) для ка- нала Поля рассчитывается по формуле [
42
]
EFR
Polya
(m) =

R
R
+ S

m
∏
j
=1
S + ( j − 1)∆
R
+ S + j∆

(9.23)
87

Нереалистичность канала Поля заключается в его бесконечной памя- ти — каждый «вытащенный из урны» красный шар, хоть первый, хоть милли- онный, приводит к одному и тому же увеличению количества красных шаров
[
55
]. В связи с этим в работе [
55
] предлагается модель канала Поля с конеч- ной памятью, в которой влияние каждого вытащенного шара ограничено по времени.
Принцип работы канала Поля с конечной памятью заключается в сле- дующем. В урне изначально содержится T шаров, из которых R красных и S
черных, так что T = R + S. На каждом j-м шаге ( j = 1, 2, . . .) из урны вытаски- вается шар и затем заменяется набором из ∆ + 1 шаров того же цвета (∆ > 0).
Через M шагов, на ( j + M)-м шаге из урны изымаются те ∆ шаров, что были добавлены на j-м шаге. Параметры ρ, σ и δ вычисляются аналогично обыч- ному каналу Поля. Влияние вытащенных шаров на канал также описывается формулой (
9.20
). В итоге, после периода инициализации канала длиной M ша- гов, общее число шаров в урне фиксируется и становится равным (T + M∆)
[
55
].
9.7. Канал с аддитивным белым гауссовским шумом
Канал с аддитивным белым гауссовским шумом
10
(АБГШ) получает- ся из канала ДКБП при бесконечном уровне квантования выхода детектора
(Q = ∞) [
39
]. В этом случае шум является гауссовской случайной величиной с нулевым средним и дисперсией, равной
σ
2
=
1 2 ·
E
b
N
0
,
где
E
b
N
0
— нормированное отношение сигнал-шум в канале АБГШ.
Таким образом, канал АБГШ характеризуется дискретным входом X =
{x
0
, . . . , x q
−1
}, непрерывным выходом Y = {−∞, +∞} и переходными вероят- ностями:
P
(y|x j
) =
1
√
2πσ
2
e
−
(y−x j)
2 2σ 2
,
j
= 0, 1, . . . , q − 1.
(9.24)
Для канала АБГШ зависимость вероятности ошибки p
0
от нормирован- ного отношения сигнал-шум
E
b
N
0
определяется в соответствии с выражением
(
9.5
).
Модель канала АБГШ широко применяется при расчёте и моделирова- нии многих систем радиосвязи, особенно при моделировании каналов спут- никовой и дальней космической связи [
56
].
10
В зарубежной литературе используется англоязычный термин Additive White Gaussian Noise (AWGN).
88

Поскольку в помехоустойчивом кодировании работа производится с дискретными данными, при проведении моделирования с использованием ка- нала АБГШ (и других аналоговых каналов) перед передачей закодированных данных в канал необходимо проводить процедуру манипуляции, а после при- ема данных из канала — обратную процедуру. При работе с двоичными дан- ными часто используется двоичная фазовая манипуляция
11
(ФМн-2).
Контрольные вопросы

1. Дайте понятие двоичного-симметричного канала. Как рассчитывает- ся его пропускная способность?
2. Что такое двоичный симметричный канал со стираниями?
3. Опишите модель канала Гилберта–Эллиотта.

4. Что такое канал Поля?
11
В зарубежной литературе используется англоязычный термин Phase shift keying modulation (PSK).
89

ЗАКЛЮЧЕНИЕ
В пособии рассмотрены математические основы теории помехоустой- чивых кодов. Приведены и рассмотрены на примерах алгоритмы, использую- щиеся при построении кодирующих и декодирующих устройств.
Ввиду ограниченного объема пособия в нем не был рассмотрен такой важный вопрос, как оценка эффективности применения помехоустойчивых кодов в системах передачи данных. Тем не менее, изучив математический ап- парат помехоустойчивых кодов будущие специалисты в области телекомму- никаций смогут успешно справиться с этой задачей.
90

СПИСОК ЛИТЕРАТУРЫ
[1] Шварцман, В.О. Теория передачи дискретной информации: Учебник для вузов свя- зи. / В.О. Шварцман, Г.А. Емельянов. — М. : Связь, 1979.
[2] Кларк, Д.К. Кодирование и исправление ошибок в системах цифровой связи /
Д.К. Кларк, Д.Б. Кейн. Статистическая теория связи. — М. : «Радио и Связь», 1987.
[3] Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стираю- щем канале связи / А.А. Гладких. — Ульяновск : УлГТУ, 2010.
[4] Когновицкий, О.С. Основы циклических кодов. Учебное пособие / О.С. Когновиц- кий. — Л. : ЛЭИС, 1990.
[5] Ковриженко, Г.А. Системы счисления и двоичная арифметика: От счета на пальцах до ЭВМ / Г.А. Ковриженко. — К. : Рад. шк., 1984.
[6] Фомин, С.В. Системы счисления / С.В. Фомин. — 5-е изд. — М. : Наука, 1987.
[7] Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер. — 2-е изд. — М. : Наука, 1966.
[8] Ланкастер, П. Теория матриц: Пер. с англ / П. Ланкастер. — 2-е изд. — М. : Наука,
1982.
[9] Gray, R.M. Toeplitz and Circulant Matrices: A Review / R.M. Gray //
Foundations and
Trends in Communications and Information Theory
. — 2006. — Vol. 2, no. 3. — P. 155–
239.
[10] Ежов, И.И. Элементы комбинаторики / И.И. Ежов, А.В. Скороход, М.И. Ядренко. —
М. : Наука, 1977.
[11] Корн, Г. Справочник по математике для научных работников и инженеров / Г. Корн,
Т. Корн. — М. : Наука, 1973.
[12] Винберг, Э.Б. Алгебра многочленов / Э.Б. Винберг. — М. : Просвещение, 1980.
[13] Теория электрической связи: учебное пособие / К.К. Васильев, В.А. Глушков,
А.В. Дормидонтов, А.Г. Нестеренко ; Под ред. К.К. Васильева. — Ульяновск : УлГ-
ТУ, 2008. — ISBN:
978-5-9795-0203-8
[14] Постников, М.М. Основы теории Галуа / М.М. Постников. — М. : Физматгиз, 1960.
[15] Постников, М.М. Теория Галуа / М.М. Постников. — М. : Физматгиз, 1968.
[16] Чеботарёв, Н.Г. Основы теории Галуа. Часть 1 / Н.Г. Чеботарёв. — М.-Л. : ОНТИ,
1934.
[17] Чеботарёв, Н.Г. Теория Галуа. Книга 1 / Н.Г. Чеботарёв ; Под ред. И.М. Виноградо- ва. — М.-Л. : ОНТИ, 1936.
[18] Чеботарёв, Н.Г. Основы теории Галуа. Часть 2 / Н.Г. Чеботарёв. — М.-Л. : ОНТИ,
1937.
[19] Лидл, Р. Конечные поля: В 2-х т. : Пер. с англ / Р. Лидл, Г. Нидеррайтер ; Под ред.
В.И. Нечаева. — М. : Мир, 1988. — ISBN:
978-5-0300-0064-0
[20] Когновицкий, О.С. Двойственный базис и его применение в телекоммуникациях /
О.С. Когновицкий. — СПб. : Линk, 2009. — ISBN:
978-5-98595-020-5 91