Inf 14
Затронутые темы
Inf 14
Затронутые темы
Думачев В.Н.
ТЕОРИЯ ИНФОРМАЦИИ
И КОДИРОВАНИЯ
Воронеж - 2012
УДК 519.72
Д82
1203021300 - 39
Д 1(III) УДК 519.72
221 - 08
1 Энтропия и информация 5
1.1 Энтропия и информация дискретных источников сообщений . . . . . 5
1.2 Энтропия непрерывных источников сообщений . . . . . . . . . . . . . 10
1.3 Условная энтропия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Задачи информационного поиска . . . . . . . . . . . . . . . . . . . . . 20
1.5 Взаимная информация . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6 Кодирование информации методом Шеннона . . . . . . . . . . . . . . 35
1.7 Избыточность сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Каналы связи 41
2.1 Пропускная способность каналов связи . . . . . . . . . . . . . . . . . . 41
2.2 Теоремы Котельникова и Шеннона . . . . . . . . . . . . . . . . . . . . 58
2.3 Теория массового обслуживания . . . . . . . . . . . . . . . . . . . . . . 61
2.3.1 Цепи Маркова . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.2 Работа телефонного коммутатора . . . . . . . . . . . . . . . . . 64
2.3.3 Система массового обслуживания с ожиданием . . . . . . . . . 72
2.4 Стандарт сотовой связи GSM . . . . . . . . . . . . . . . . . . . . . . . 74
2.5 Стандарты зписи CD и DVD . . . . . . . . . . . . . . . . . . . . . . . . 80
3
4 Оглавление
Энтропия и информация
5
6 Глава 1. Энтропия и информация
несет (мы и так знали, что оно появится). Например, если кто то вам скажет, что
занятия в нашем институте начинаются в 9-00, то для вас это не будет новостью,
вероятность этого события равна 1 и вы не получите в этом сообщении никакой до-
полнительной информации о системе образования в нашем вузе. Рассмотрим другой
крайний случай: допустим, стало известно, что всем двоечникам в нашем ВУЗе будут
давать дополнительный отпуск и надбавку к стипендии. Вот это уже новость. Эту
новость все будут друг другу пересказывать, опубликуют в газетах, возможно даже
приедет телевидение. Ведь появление такого события очень маловероятно, поэтому
оно очень значимо с точки зрения информации и дает огромные знания относительно
того, как (оказывается) организован учебный процесс в нашем институте. Из этого
примера видно, что вероятность появления события должна играть ключевую роль
в формальном определении информации. В математике за меру информации прини-
мают величину
1
I = log2 = − log2 p.
p
Заметим, что в теории информации используется двоичный (битовый) логарифм
log2 a
I = − ln p.
I(x) = − ln f (x).
Единица измерения информации называется бит (1 bit или 1 b). Бит – информация,
хранящаяся в 1 ячейке с двумя значениями (0,1):
x 0 1
p 0.5 0.5
Тогда
1
I0 = − ln p0 = − log2 = log2 2 = 1 bit,
2
1.1. Энтропия и информация дискретных источников сообщений 7
1
I1 = − ln p1 = − log2 = log2 2 = 1 bit.
2
1
I = − ln p = − ln = ln 2 = 1 bit
2
т.е. 1 бит информации. N
8 7 6 7
p= · · = = 0.467.
10 9 8 15
Количество информации в сообщении определяется по формуле
1 15
I = ln = ln = 1.1 bit. N
p 7
имеем выбираем
Отличники n1 = 4 m1 = 3
Хорошисты n2 = 6 m2 = 1
Троечники n3 = 7 m3 = 1
Двоечники n4 = 3 m4 = 0
Всего N=20 M=5
Вспоминая, что
n!
Cnm = ,
m!(n − m)!
8 Глава 1. Энтропия и информация
Задача 1.1.
12. В урне 3 белых, 4 черных и 5 красных шаров. Из урны вынимают сразу три
шара. Какое количество информации содержится в сообщении о том, что все
шары будут разного цвета.
13. В урне 5 белых, 6 черных и 7 красных шаров. Из урны вынимают сразу три
шара. Какое количество информации содержится в сообщении о том, что все
шары будут белые.
14. Имеются изделия четырех сортов, причем число изделий каждого сорта равно
n1 = 2, n2 = 3, n3 = 1, n4 = 3. Для контроля наудачу берутся 5 изделий. Какое
количество информации содержится в сообщении о том, что среди них m1 = 2
первосортных, m2 = 1 второго, m3 = 0 третьего и m4 = 2 четвертого сорта.
I = − ln f (x).
а для дискретной: X
H(x) = − pi ln pi .
причем f ln f = 0, если f = 0.
Свойства энтропии.
1. H(x) ≥ 0;
2. H(x) ≤ ln |x|;
3. Если x и y независимы, то H(xy) = H(x) + H(y)
4. Обработка информации не приводит к увеличению энтропии
H(g(x)) ≤ H(x).
ZZ
Hy (x) = − f (y)f (x/y) ln f (x/y)dxdy.
Если x и y независимы, то
Iy (x) = Ix (y).
n n n
X X 1 1 1 X 1
H(x) = − pi · ln pi = − · ln = · ln n 1 = · ln n · n = ln n. N
i=1 i=1
n n n i=1
n
1.2. Энтропия непрерывных источников сообщений 13
y Лемма 1. (Гиббс)
y=x-1 Для любых p и q, таких что
X X
p = 1, q=1
y=ln x
имеет место неравенство
X X
0 1 x p · ln p ≥ p · ln q.
получим p · ln pq ≤ 0, или
P
X q X
p · ln = p · (ln q − ln p) ≤ 0.
p
Отсюда следует утверждение леммы.
H(x) ≤ ln n.
2) ограничением на дисперсию
Z
(x − x)2 f (x)dx = D.
F (f, λ, µ) = f ln f + λ · f + µ · (x − x)2 f
дает r Z
µ 2 1
(x − x)2 e−µ·(x−x) dx = =D
π 2µ
1.2. Энтропия непрерывных источников сообщений 15
или
1
µ= ,
2D
тогда r
1 (x−x)2
f= e− 2D . N
2πD
1. Среди всех законов распределения непрерывной случайной величины x, опре-
деленных на интервале a ≤ x ≤ b, найти закон распределения с максимальной
1
энтропией. f = b−a
получим выражения
X XX
H(x) = − p(x) · ln p(x) = − p(x, y) · ln p(x),
x y x
16 Глава 1. Энтропия и информация
X XX
H(y) = − p(y) · ln p(y) = − p(x, y) · ln p(y).
y x y
Тогда
XX
H(x) + H(y) = − p(x, y) · (ln p(x) + ln p(x))
y x
XX XX
= − p(x, y) · ln (p(x)p(y)) = − p(x, y) · ln q(xy).
y x y x
Здесь мы ввели обозначение q(xy) = p(x)p(y). Теперь, используя лемму Гиббса, по-
лучим
XX XX
H(x, y) = − p(x, y)·ln p(x, y) ≤ − p(x, y)·ln q(x, y) = H(x)+H(y).
x y x y
p(y, x) = p(x)p(y|x),
мы получим
X XX
H(y|x) = p(xi )H(y|xi) = − p(xi , yk ) · ln p(yk |xi ).
i i k
1.3. Условная энтропия 17
Теорема 3.
H(x, y) = H(x) + H(y|x) = H(y) + H(x|y)
Доказательство. По определению
XX XX
H(x, y) = − p(x, y) · ln p(x, y) = − p(x, y) · ln p(x)p(y|x)
x y x y
XX XX
= − p(x, y) · ln p(x) − p(x, y) · ln p(y|x)
x y x y
X X X
= − p(x) · ln p(x) − p(x) p(y|x) · ln p(y|x) = H(x) + H(y|x).
x x y
Теорема 4.
H(y|x) ≤ H(y)
Доказательство. По определению
H(x, y) = H(x) + H(y|x), H(y|x) = H(x, y) − H(x).
Но согласно теореме 2
H(x, y) ≤ H(x) + H(y)
или
H(x, y) − H(x) ≤ H(y),
тогда
H(y|x) = H(x, y) − H(x) ≤ H(y).
Условная энтропия случайной величины x относительно случайной величины y
дается выражениями X
H(x/y) = − p(x/y) ln p(x/y),
Z
H(x/y) = − f (x/y) ln f (x/y)dx.
ZZ
Hy (x) = − f (y)f (x/y) ln f (x/y)dxdy.
Iy (x) = Ix (y).
1 1 2 2 1 1
H1 = − · ln + · ln + · ln
4 4 4 4 4 4
1 1
= − (1 · ln 1 + 2 · ln 2 + 1 · ln 1) + ln 4 = − (0 + 2 + 0) + 2 = 1.5;
4 4
27 27 27 27 9 9 1 1
H2 = − · ln + · ln + · ln + · ln
64 64 64 64 64 64 64 64
1
= ln 64 − (27 · ln 27 + 27 · ln 27 + 9 · ln 9 + 1 · ln 1)
64
∼ 1
= 6− (27 · 4.75 + 27 · 4.75 + 9 · 3.17 + 1 · 0) = 4.45.
64
Поскольку H1 < H2 - то исход стрельбы по первой мишени обладает большей
определенностью. N
1.3. Условная энтропия 19
№ k1 b1 c1 k2 b2 c2 № k1 b1 c1 k2 b2 c2
1 10 5 5 7 7 6 16 1 15 4 15 5 0
2 12 4 4 6 6 8 17 2 14 4 14 6 0
3 14 2 2 8 8 4 18 3 13 4 13 5 2
4 1 16 1 10 5 5 19 4 12 4 12 4 4
5 18 0 2 5 12 3 20 5 11 4 11 3 6
6 4 8 8 1 10 9 21 6 10 4 10 2 8
7 5 4 11 2 8 10 22 7 9 4 9 1 10
8 6 3 11 3 7 10 23 8 8 4 8 2 10
9 7 2 11 4 6 10 24 9 7 4 7 3 10
10 5 10 5 6 7 7 25 10 6 4 6 14 0
11 8 1 11 5 2 13 26 11 5 4 5 13 2
12 9 2 9 7 3 10 27 12 4 4 4 12 4
13 10 3 7 8 4 8 27 13 3 4 3 11 6
14 11 4 5 8 5 7 29 14 2 4 2 10 8
15 5 5 10 7 6 7 30 15 1 4 1 9 10
Дополнительные упражнения
λk
Пуассона Pn (k) = k!
e−λ
∞
e X λk −λ
H(x) = λ ln + e ln(k!)
λ k=1 k!
Равномерный Pn (k) = 1
n
H(x) = ln n
k 1(1+α)...[1+(k−1)α]
Полиа Pn (k) = P0 λ
1+αλ
× k!
1 + αλ
H(x) = −λ ln λ + ln(1 + αλ)
α
∞ k
X λ 1(1 + α)...[1 + (k − 1)α] 1(1 + α)...[1 + (k − 1)α]
− P0 × ln
k=1
1 + αλ k! k!
0 0 1
1 0 0 0 1 0
0 0 1 0 0 1
N
I ln 8 3
n= = = ≈ 1.893 ' 2,
I0 ln 3 1.6
т.е. оно не меньше двух (с точки зрения теории информации). К сожалению, пока не
известен алгоритм решения этой задачи с помощью 2-ух взвешиваний. N
x −1 0 1
p 1/2 0 1/2
и найдем ее энтропию
1 1 1 1
H=− ln + 0 · ln 0 + ln = ln 2 = 1 bt.
2 2 2 2
Т.е. мы получили 1 bt. информации, а энтропия системы была 3 bt. Т.е. с помощью
взвешивания мы уменьшили неопределенность системы до 2 bt. и у нас осталось еще
одно взвешивание, которое в идеале может дать только ln 3 ' 1.585 bt. Очевидно что
оставшегося взвешивания нам недостаточно для решения задачи.
Рассмотрим другую стратегию. Положим на обе чашки по 1 монете. Тогда ре-
зультат взвешивания дает три возможных исхода с вероятностями:
1) x = −1 - перевесила левая чашка, p(-1)=1/4;
2) x = 0 - чашки остались в равновесии, p(0)=1/2;
3) x = 1 - перевесила правая чашка, p(1)=1/4.
Построим таблицу распределения случайной величины x
x −1 0 1
p 1/4 1/2 1/4
1.4. Задачи информационного поиска 23
и найдем ее энтропию
1 1 1 1 1 1
H=− ln + ln + ln = 1.5 bt.
4 4 2 2 4 4
Т.е. нам осталось получить еще 1.5 bt. информации о системе с помощью одного
оставшегося взвешивания. В принципе, это возможно, поскольку при удаче одно взве-
шивание может нам дать ln 3 ' 1.585 bt. информации.
Если в результате первого взвешивания одна из чашек перевесила, то мы точно
знаем, что на столе лежат настоящие монеты. Меняя одну любую монету на весах с
настоящей мы получим таблицу распределения для второго взвешивания
x −1 0 1
p 1/4 1/2 1/4
с энтропией
H = 1.5 bt.
Т.е. задача решена.
Однако, если в результате первого взвешивания чашки весов остались в равно-
весии, то фальшивая монета осталась на столе. Но для того, чтобы определить ее
необходимо
I ln 4
n= = ≈ 1.262 > 1,
I0 ln 3
т.е. больше одного взвешивания1 . N
Пример 1.10. Имеется 5 монет одного достоинства; 1 из них фальшивая. Какое
наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить
фальшивую монету и выяснить, легче она или тяжелее чем остальные?
Решение. Каждая из 5 монет может оказаться фальшивой и быть при этом
тяжелее или легче остальных. Таким образом имеется N = 2 · 5 = 10 возможных
исходов. Поэтому выбор отдельно взятой монеты дает информацию, равную
1 1
I = − ln p = − ln
= − ln = ln 10 ≈ 3.322 bit.
N 10
Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и
равновесие. Поэтому произвольное единичное взвешивание дает информацию
1
I0 = − ln= ln 3 ≈ 1.6 bit.
3
Следовательно, минимальное число взвешиваний не может быть меньше, чем
I ln 10 3.322
n= = = ≈ 2.096 < 3,
I0 ln 3 1.6
т.е. оно не меньше трех.
Схема решения этой задачи следующая. Положим на обе чашки по 1 монетке.
1
Мы сможем найти фальшивую монету, но не сможем определить легче она или тяжелее насто-
ящих.
24 Глава 1. Энтропия и информация
0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 N
I ln 12
n= = = log3 12 ≈ 2.262 < 3,
I0 ln 3
т.е. оно не меньше трех.
Схема решения этой задачи следующая.
Определим количество монет которое необходимо положить на весы при первом
взвешивании, т.е. рассчитаем стратегию взвешивания используя методы теории ин-
формации. Чтобы число взвешиваний было наименьшим, каждое взвешивание долж-
но давать наибольшее количество информации, т.е. исход взвешивания должен обла-
дать наибольшей энтропией. Введем случайную величину x положение чашки весов
при взвешивании x = (−1; 0; 1).
Пусть при первом взвешивании на обе чашки положено по i монет. При этом
возможны три исхода:
x −1 0 1
i=1 p 1/6 4/6 1/6
i=2 p 2/6 2/6 2/6
i=3 p 3/6 0 3/6
1 1
I = − ln p = − ln = − ln = ln 24 ≈ 4.6 bit.
N 24
Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и
равновесие. Поэтому произвольное единичное взвешивание дает информацию
1
I0 = − ln = ln 3 ≈ 1.6 bit.
3
26 Глава 1. Энтропия и информация
ln 12 ≈ 3.57 ∼
=4
взвешиваниями:
xi −1 0 1
pi 12i 12−2i
12
i
12
№ i k p1 p2 p3 Hik [x]
1 1 1 0.25 0.5 0.25 0.452
2 1 0 0.125 0.75 0.125 0.320
3 2 2 0.5 0 0.5 0.301
4 2 1 0.375 0.25 0.375 0.470
5 2 0 0.25 0.5 0.25 0.452
6 3 1 0.5 0 0.5 0.301
7 3 0 0.375 0.25 0.375 0.470
8 4 0 0.5 0 0.5 0.301
i1 = 1, i2 = 2, j1 = 0, j2 = 2.
а) весы в равновесии;
б) перевешивает левая чашка;
в) перевешивает правая чашка.
В случае а) - равновесия мы точно знаем вес фальшивки (тяжелая фальшивка), а
сама фальшивка находится в трех оставшихся монетах группы L. Третьего взвеши-
вания в составе 1:1 из монет группы L нам достаточно, чтобы ее обнаружить.
В случае б): Третье взвешивание есть разбиение j2 = 2 в составе 1:1 на обе чашки
весов:
Дополнительные упражнения
№ проверки № состояния
1 2 3 4 5
1 0 0 0 0 1
2 0 0 0 1 1
3 0 1 1 0 0
4 1 0 1 0 0
5 1 0 1 0 1
6 1 1 1 0 0
7 1 1 1 1 0
Вычисляем энтропию
X 3 3 1 1
H(x) = − px · ln px = − ln + ln = 0.811
4 4 4 4
X 5 5 3 3
H(y) = − py · ln py = − ln + ln = 0.954
8 8 8 8
X 1 1 1 1 1 1 1 1
H(x, y) = − pxy · ln pxy = − ln + ln + ln + ln = 1.75
2 2 8 8 4 4 8 8
и взаимную информацию.
Пример 1.14. (Ash [12]) Имеются две монеты. Одна из монет правильная, а у
другой – два герба. Монета выбирается случайным образом, дважды подбрасывает-
ся, а результат записывается. Спрашивается, как много информации относительно
идентичности монет мы можем получить, подсчитывая количество выпавших орлов?
Очевидно, что количество орлов должно нам что-то сообщить о природе монеты.
Решение. Обозначим через x – случайную величину, определяющую выбранную
монету (x = 0 - правильная, x = 1 - фальшивая). Вероятность выбора правильной
или фальшивой монеты одинакова: p(x = 0) = p(x = 1) = 1/2.
Обозначим через y количество выпавших гербов при двух подбрасываниях вы-
бранной монеты. Поскольку y зависит от того какую монету мы взяли (правильную
или фальшивую), мы получим два условных закона распределения
1/4
y 0 1 2 0
x=0:
p 1/4 1/2 1/4 1/2 0
1/2
y 0 1 2 1
x=1: 1/4
p 0 0 1/2
1/2 1
1 2
1.5. Взаимная информация 31
p(x, y) = p(x)p(y|x)
или
1 1 1 1 1 1 1 1 1
2·4 ·
2 2
·
2 4 8 4 8
p(x, y) = = .
1 1 1 1
·0 ·0 ·1 0 0
2 2 2 2
Складывая вероятности по строкам и столбцам, получим редуцированные (марги-
нальные) законы распределения p(x) и p(y):
xy 0 1 2 p(x)
0 1/8 1/4 1/8 1/2
1 0 0 1/2 P1/2
p(y) 1/8 1/4 5/8 =1
где
X 1 1 1 1 1 1
H(x) = − p(x) ln p(x) = − · ln − · ln = · 1 + · 1 = 1 bit,
x
2 2 2 2 2 2
X 1 1 1 1 5 5 3 2 0.678
H(y) = − p(y) ln p(y) = − · ln − · ln − · ln = + + = 1.3 bit,
y
8 8 4 4 8 8 8 4 8
XX
H(x, y) = − p(x, y) ln p(x, y)
x y
1 1 1 1 1 1 1 1
= − · ln − · ln − · ln − 0 · ln 0 − 0 · ln 0 − · ln
8 8 4 4 8 8 2 2
3 2 3 1 14
= + + +0+0+ = = 1.75 bit.
8 4 8 2 8
Тогда
I(x|y) = H(x) + H(y) − H(x, y) = 1 + 1.3 − 1.75 = 0.55 bit. N
14. Иван и Петр наудачу извлекают по одному шару из урны, содержащей 6 бе-
лых и 4 черных шара. Иван извлекает шар первым. Случайные величины: x -
количество белых шаров у Ивана, y - количество белых шаров у Петра
15. Решить предыдущую задачу при условии, что шары извлекаются с возвраще-
нием.
20. Случайная величина x принимает значения (0; 1; 2) с вероятностями (0.3; 0.7; 0.1),
а независящая от нее случайная величина y - значения (−1; 0; 1) с вероятно-
стями (0.3; 0.5; 0.2).
22. Из урны, содержащей 6 белых и 4 черных шара наудачу извлекают 2 шара без
возвращения. Случайные величины: x - число извлеченных белых шаров, y -
число черных шаров в выборке.
23. Число x выбирается случайным образом из множества целых чисел (1, 2, 3).
Затем из того же множества выбирается наудачу число y, большее первого или
равное ему.
24. Бросается два раз игральная кость. Случайные величины x - появление ше-
стерки, y - появление единицы.
25. Два раза бросается монета. Случайные величины x - появление орла, y - появ-
ление решки.
26. Три раза бросается монета. Случайные величины x - появление орла, y - появ-
ление решки.
27. Бросается один раз игральная кость. Если на грани выпадает цифра 1, 2, 3 или
4, то монета бросается 1 раз. В противоположном случае – монета бросается 2
раза. Случайные величины: x - появление цифры 1,2,3 или 4, y – количество
выпавших орлов на монете.
34 Глава 1. Энтропия и информация
№ n № n
1 23 2 1 15 3 2 1 1 16 4 1 2 0 2 0 0 4
2 2 20 1 20 3 0 1 5 17 2 1 1 13 2 2 5 22
3 1 1 2 3 11 1 23 2 18 23 2 1 15 1 1 9 3
4 6 1 0 3 20 1 2 20 19 2 23 1 12 3 9 1 1
5 2 1 1 3 15 1 21 2 20 1 1 1 2 3 11 11 23
6 2 21 1 14 3 1 1 2 21 1 1 6 3 13 2 23 2
7 2 0 1 13 3 2 3 21 22 2 2 1 14 2 2 5 22
8 2 1 2 3 14 1 23 2 23 3 20 1 20 3 4 3 1
9 1 0 6 3 20 2 21 2 24 3 20 12 20 3 4 3 1
10 2 20 2 20 3 6 0 1 25 3 20 12 20 3 4 3 3
11 2 0 1 13 3 2 5 22 26 23 2 1 15 3 2 1 1
12 6 3 20 2 23 2 2 0 27 2 20 1 20 3 0 1 5
13 20 2 22 2 3 6 0 2 28 6 1 0 3 20 1 2 20
14 2 2 1 15 3 1 5 25 29 2 0 1 13 3 2 3 21
15 23 2 1 16 1 7 3 1 30 2 1 2 3 14 1 23 2
1.6. Кодирование информации методом Шеннона 35
математика_-_царица_наук
x А _ Ц К И М Т Е Р Н У -
n 0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04
Разобьем таблицу на две группы таким образом, чтобы сумма вероятностей по-
явления символов в каждой группе была приблизительно одинаковой. Пометим
все буквы попавшие в первую группу символом 0, а все буквы попавшие во вторую
группу символом 1.
0.64 0.36
А _ Ц К И М Т Е Р Н У -
0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04
0 1
Аналогично, разбиваем первую группу на две равные по вероятностям части и при-
сваиваем первой группе символ 0, а второй группе – символ 1 и.т.д.
А _ Ц К И М Т Е Р Н У -
0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04
0 1
0 1 0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1
Объединяя символы для каждой буквы получим кодовую таблицу
А 000 И 011 Р 1100
_ 001 М 100 Н 1101
Ц 0100 Т 1010 У 1110
К 0111 Е 1011 - 1111
Экономность кода – количество информации, приходящееся на один кодовый
символ, вычисляется как отношение энтропии алфавита к математическому ожи-
данию длины кодового обозначения букв сообщения. В нашем случае буквам сооб-
щения соответствуют коды длиной 3 символа для букв (А, _, И, М) и 4 символа -
для остальных 8-ми букв. Распределение вероятностей появления кода данной длины
дано в таблице
x 3 4
n 4 8
p 1/3 2/3
Таким образом, математическое ожидание длины закодированной буквы есть
X 1 2 11 ∼
M[n] = xi pi = 3 · + 4 · = = 3.67.
3 3 3
Для экономности кода получим
H(x) 3.3
S= = = 0.899. N
M(n) 3.67
1.7. Избыточность сообщения 37
x\y м н о г е n(x)
м 0 1 0 0 0 1
н 0 0 2 0 0 2
о 0 1 0 2 1 4
г 0 0 2 0 0 2
е 1 0 0 0 0 1
n(y) 1 2 4 2 1
P
= 10
H(x, y)
Следовательно H2 = = 1.195 bit,
2
H2 1.195
R2 = 1 − =1− ≈ 0.485 bit. N
ln N 2.322
Пример 1.18. Алфавит состоит из 8 букв (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ), вероят-
8 4 2 1 1 1 1
ности появления которых равны: 16 , 16 , 16 , 16 , 16 , 16 , 16 , 0 . Найти избыточность R1
источника сообщений при статистической независимости букв.
Решение. По определению избыточности имеем
H1 H1
R1 = 1 − =1−
H0 ln N
Поскольку мы имеем всего N=8 различных символов, то
H0 = ln N = ln 8 = 3 bit,
1.7. Избыточность сообщения 39
4
X
H1 = − pi ln pi =
i=1
8 8 4 4 2 2 1 1
= − · ln + · ln + · ln +4· · ln + 0 · ln 0
16 16 16 16 16 16 16 16
8 4 2 1 8 + 8 + 6 + 16
= ·1+ ·2+ ·3+4· ·4+0 = = 2.375 bit
16 16 16 16 16
и
2.375
R1 = 1 − = 0.208. N
3
Задача 1.6. Найти:
а) избыточность R1 источника сообщений при статистической независимости букв;
б) избыточность R2 c учетом зависимости между буквами.
для сообщения
№ сообщение № сообщение № сообщение
1 атомизатор 11 даунтаун 21 клочочек
2 менеджмент 12 плодовод 22 волнолом
3 кавказка 13 шаровары 23 воздуховоз
4 барбарис 14 эстафета 24 подлодка
5 берберин 15 прототип 25 размазня
6 варварка 16 прививка 26 гонгконг
7 колокол 17 прабабка 27 колокольня
8 женьшень 18 пленение 28 математик
9 чихуахуа 19 метатанк 29 постылость
10 наносность 20 ленинизм 30 водопровод
Глава 2
Каналы связи
41
42 Глава 2. Каналы связи
При этом
H(xy) = H(x) + H(y).
Средняя взаимная информация связана с энтропией соотношениями
I(x; y) ≤ H(x),
I(x; y) ≤ H(y).
Скорость передачи Vk – среднее количество информации, получаемое за единицу
времени:
Vk = F I(x; y) = F [H(x) − H(x/y)] = F [H(y) − H(y/x)]
При отсутствии помех множества событий x и y статистически полностью взаимно
зависимы, т. е. H(x/y) = H(y/x) = 0, следовательно,
error source
x y
encoding decoding
data channel
44 Глава 2. Каналы связи
Здесь
X
H(x) = − p(x) · ln p(x) = −p · ln p − p · ln p,
x
X
H(y) = − p(y) · ln p(y) = −(p · β + p · β) · ln(p · β + p · β)
y
= −pβ · ln pβ − pβ · ln pβ − pβ · ln pβ − pβ · ln pβ .
Тогда
(p · β + p · β) β − pβ + p − pβ
= 1, или =1
(p · β + p · β) pβ + 1 − p − β + pβ
откуда
1
2β − 4pβ + 2p = 1 т.е. p∗ = .
2
46 Глава 2. Каналы связи
1 1 1
p(x2 , y1 ) = p(x2 )α = · = ;
4 8 32
1 7 7
p(x2 , y2 ) = p(x2 )α = · = .
4 8 32
Составим таблицу совместного распределения для передаваемых и получаемых сиг-
налов
x\y 0 1 p(x)
21 3 24
0 32 32 32
= 34
1 7 8
1 32 32 P32
= 14
p(y) 22
32
10
32
p=1
1. По формулам для среднего количества информации
X 3 3 1 1
H(x) = − p(xi ) ln p(xi ) = − ln − ln = 0.811 bit
i
4 4 4 4
X 22 22 10 10
H(y) = − p(yi ) ln p(yi ) = − ln − ln = 0.896 bit
i
32 32 32 32
XX 21 21 3 3 1 1 7 7
H(x, y) = − p(x, y) ln p(x, y) − ln − ln − ln − ln
32 32 32 32 32 32 32 32
= 1.355 bit
I(x, y) = H(x) + H(y) − H(x, y)
X X XX
= − p(x) ln p(x) − p(y) ln p(y) + p(x, y) ln p(x, y)
3 3 1 1 22 22 10 10
= − ln − ln − ln − ln
4 4 4 4 32 32 32 32
21 21 3 3 1 1 7 7
+ ln + ln + ln + ln = 0.352 bit
32 32 32 32 32 32 32 32
x y
7/8
p 0 0
1/8
1/8
q 1 1
7/8
налов
x\y 0 1 p(x)
7 1
0 p8 p8 p
1 7
1 q8 q8 P q
p(y) p 87 + q 18 p 18 + q 87 p=1
По формулам для среднего количества информации
X X
H(x) = − p(xi ) ln p(xi ) H(y) = − p(yi) ln p(yi)
i i
XX
H(x, y) = − p(x, y) ln p(x, y)
7 7 1 1
C =1+ ln + ln = 0.456 bit.
8 8 8 8
2.1. Пропускная способность каналов связи 49
N p α N p α N p α
1 0.1 0.91 11 0.15 0.80 21 0.23 0.70
2 0.2 0.92 12 0.25 0.81 22 0.33 0.71
3 0.3 0.93 13 0.35 0.82 23 0.43 0.72
4 0.4 0.94 14 0.45 0.83 24 0.53 0.73
5 0.5 0.95 15 0.55 0.84 25 0.63 0.74
6 0.6 0.96 16 0.65 0.85 26 0.73 0.75
7 0.7 0.97 17 0.75 0.86 27 0.83 0.76
8 0.8 0.98 18 0.85 0.87 28 0.93 0.77
9 0.9 0.99 19 0.95 0.88 29 0.03 0.78
10 0.95 0.90 20 0.05 0.89 30 0.93 0.79
α y1 α
p1 z1
1−α 1−α
1−α 1−α
y2
p2 z2
α α
50 Глава 2. Каналы связи
N p α N p α N p α
1 0.1 0.91 11 0.15 0.80 21 0.23 0.70
2 0.2 0.92 12 0.25 0.81 22 0.33 0.71
3 0.3 0.93 13 0.35 0.82 23 0.43 0.72
4 0.4 0.94 14 0.45 0.83 24 0.53 0.73
5 0.5 0.95 15 0.55 0.84 25 0.63 0.74
6 0.6 0.96 16 0.65 0.85 26 0.73 0.75
7 0.7 0.97 17 0.75 0.86 27 0.83 0.76
8 0.8 0.98 18 0.85 0.87 28 0.93 0.77
9 0.9 0.99 19 0.95 0.88 29 0.03 0.78
10 0.95 0.90 20 0.05 0.89 30 0.93 0.79
x\y 0 1 2 p(x)
0 p(1-3e) pe 2pe p
1 qs q(1-4s) 3qs Pq
p(y) p(1-3e)+qe pe+ q(1-4s) 2pe+3qs =1
x\y 0 1 2 p(x)
0 0.7p 0.1p 0.2p p
1 0.2q 0.2q 0.6q Pq
p(y) 0.7p+0.2q 0.1p+0.2q 0.2p+0.6q =1
Тогда
Hx (p) = − (p ln p + q ln q = p ln p + (1 − p) ln(1 − p)) ;
Hxy (p) = −(0.7p) ln(0.7p) + (0.1p) ln(0.1p) + (0.2p) ln(0.2p) + (0.2q) ln(0.2q)
+ (0.2q) ln(0.2q) + (0.6q) ln(0.6q)
Hxy (p) = −(0.7p) ln(0.7p) + (0.1p) ln(0.1p) + (0.2p) ln(0.2p) + 0.2(1 − p) ln(0.2(1 − p))
+ 0.2(1 − p) ln(0.2(1 − p)) + 0.6(1 − p) ln(0.6(1 − p))
x\y 0 1 2 p(x)
6 1 3
0 10
p 10
p 10
p p
2 7 1
1 10
q 10
q 10
q q
3 3 4
2 10
r 10
r 10
r Pr
6 2 3 1 7 10 3 1 4
p(y) 10
p + 10
q + 10
r 10
p + 10
q + 10
r 10
p + 10
q + 10
r =1
Тогда
Hx (p, q, r) = −(p ln p + q ln q + r ln r)
6p + 2q + 3r 6p + 2q + 3r
Hy (p, q, r) = − ln
10 10
p + 7q + 10r p + 7q + 10r
− ln
10 10
3p + q + 4r 3p + q + 4r
− ln
10 10
6p 6p p p 3p 3p
Hxy (p, q, r) = − ln − ln − ln
10 10 10 10 10 10
2q 2q 7q 7q q q
− ln − ln − ln
10 10 10 10 10 10
3r 3r 3r 3r 4r 4r
− ln − ln − ln
10 10 10 10 10 10
Given
G1(x, y) = 0 G2(x, y) = 0
xval
:= F ind(x, y)
yval
xval = 0.47 yval = 0.42
Подставляя экстремальные значения p∗ = 0.47, q ∗ = 0.42 получим пропускную спо-
собность канала связи
C = I(0.47, 0.42) = 0.227bit. N
p 0 0
q 1 1
r 2 2
yx 0 1 2 p(x)
0 p · α · α + p · 1−α2
· 12 p · α · (1 − α) + p · 1−α
2
· 12 p· 1−α
2
·1 p
1 q · 1 · 21 q · 1 · 12 0 q
2 r · 1 · 21 r · 1 · 12 0 r
p(y) pα2 + p · 1−α + q+r pα(1 − α) + p 1−α + q+r1 1−α
P
4 2 4 2
p· 2
=1
Тогда
Hx (p, q, r) = −(p ln p + q ln q + r ln r)
2 1−α q+r 2 1−α q+r
Hy (p, q, r) = − pα + p · + ln pα + p · +
4 2 4 2
1−α q+r 1−α q+r
− pα(1 − α) + p + ln pα(1 − α) + p +
4 2 4 2
1−α 1−α
− p· ln p ·
2 2
2 1−α 2 1−α q q r r
Hxy (p, q, r) = − pα + p · ln pα + p · − ln − ln
4 4 2 2 2 2
1−α 1−α q q
− pα(1 − α) + p ln pα(1 − α) + p − ln
4 4 2 2
r r 1 − α 1 − α
− ln − p· ln p ·
2 2 2 2
C учетом p + q + r = 1 запишем выражение для взаимной информации
Given
G1(x, y) = 0 G2(x, y) = 0
xval
:= F ind(x, y)
yval
xval = 0.47, yval = 0.42
56 Глава 2. Каналы связи
Вычисляем энтропию
X 1 1 1 1 1 1
H(x) = p(x) ln p(x) = − ln + ln + ln = 1.459
2 2 3 3 6 6
X 1 1 19 19 11 11
H(y) = p(y) ln p(y) = − ln + ln + ln = 1.474
2 2 60 60 60 60
X
H(xy) = p(xy) ln p(xy)
1 1 8 8 2 2 3 3 7 7
= − ln + ln + ln + ln + ln = 1.847
2 2 30 30 30 30 60 60 60 60
2.1. Пропускная способность каналов связи 57
C = F · [1 + p ln p + (1 − p) ln(1 − p)] .
Тогда
N H K F P N H K F P
1 290 4 80 0.021 16 160 4 50 0.036
2 280 5 60 0.022 17 170 3 60 0.037
3 289 3 100 0.023 18 180 4 70 0.038
4 270 4 80 0.024 19 190 3 80 0.039
5 270 2 140 0.025 20 130 7 20 0.040
6 270 4 100 0.026 21 110 6 20 0.041
7 280 3 110 0.027 22 120 4 35 0.042
8 288 2 145 0.028 23 130 3 45 0.043
9 289 2 150 0.029 24 140 4 35 0.044
10 278 2 140 0.030 25 150 3 60 0.045
11 210 3 75 0.031 26 160 4 40 0.046
12 220 4 80 0.032 27 170 3 60 0.047
13 230 3 80 0.033 28 180 4 50 0.048
14 240 4 65 0.034 29 190 3 70 0.049
15 250 3 65 0.035 30 140 4 30 0.050
C = 2F · ln(n),
Пример 2.9. Для стандартного телефоного канала без шума с F = 3kHz при
n = 2 получим
C = 2F · ln(n) = 2 · 3000 · ln(2) ' 6 kb/s,
а при n = 256:
C = 2 · 3000 · ln(256) = 6000 · 8 ' 48 kb/s. N
Задача 2.6. Пользуясь формулой Найквиста определить количество допусти-
мых уровней сигнала n в телефонном канале связи с пропускной способностью C kb/s.
N C N C N C N C N C N C N C N C N C N C
1 8 4 12 7 15 10 18 13 21 16 24 19 27 22 30 25 33 28 36
2 6 5 13 8 16 11 19 14 22 17 25 20 28 23 31 26 34 29 37
3 8 6 14 9 17 12 20 15 23 18 26 21 29 24 32 27 35 30 38
2.3. Теория массового обслуживания 61
(0) (0)
(p1 + p2 + ... + p(0)
m = 1);
pnji - вероятность j-го исхода в n-м опыте при условии, что в (n − 1) -м опыте насту-
(n) (n) (n)
пил i-й исход, (n = 2, 3, ...; i, j = 1, 2, ..., m; p1i + p2i + ... + pmi = 1). Введенными
вероятностями полностью описывается цепь Маркова.
(n)
Цепь Маркова называется однородной, если вероятность pij от n не зависят, в
этом случае они обозначаются без верхнего индекса: pij . Числа pij называются веро-
ятностями переходов, а
p11 p12 ... p1m
p21 p22 ... p2m
P = (pij ) =
...
... ... ...
pm1 pm2 ... pmm
- матрицей перехода.
По матрице перехода можно построить граф состояний, если в качестве узлов
взять состояния s = (s1 , s2 , ..., sn ) системы, а стрелками – возможные переходы из
одного состояния в другое состояние.
Например, для матрицы перехода
p11 p12 p13 0 0
p21 0 0 0 0
P =
p31 0 0 0 0
0 0 p43 0 0
0 0 p53 0 p55
Обозначим: pij (n) – вероятность того, что через n шагов произойдет переход
от sj к si (i, j = 1, 2, ..., m), P (n) – матрицу переходов за n шагов, т.е. матрицу,
состоящую из pij (n). Если в начальный момент система находилась в состоянии
s0 = (s1 , s2 , ..., sn ), то на следующем шаге она перейдет в состояние
s1 = P s0 .
На втором шаге состояние системы есть:
s2 = P s1 = P P s 0 = P 2 s0 .
Очевидно, что через n шагов состояние системы sn будет выражаться через исходное
состояние системы s0 формулой
sn = P n s0 .
Т.о. справедлива формула
P (n) = P n .
Теорема Маркова (о предельных вероятностях): если существует такое на-
туральное число n0 , что все элементы матрицы P (n0 ) = P n0 строго положительны,
то для каждого (j = 1, 2, ..., m) существует предельная вероятность lim P (n) = P ∗ .
n→∞
Предельные вероятности (если они существуют) можно найти из уравнений:
P s = s, или pij sj = δij sj , (pij − δij ) sj = 0.
Перепишем задачу в матричном виде (P − I)s = 0:
p11 − 1 p12 ... p1n s1
p21
p22 − 1 ... p2n
s2 = 0.
... ... ... ... ...
pn1 pn2 ... pnn − 1 sn
Таким образом, вместе с условием нормировки на компоненты вектора состояния,
задача на отыскание предельного состояния сводится к решению системы уравнений:
(p11 − 1)s1 + p12 s2 + ... + p1n sn = 0
p21 s1 + (p22 − 1)s2 + ... + p21 sn = 0
... .
pn1 s1 + pn2 s2 + ... + (pnn − 1)sn = 0
s1 + s2 + ... + sn = 1
2.3. Теория массового обслуживания 63
p p p p
11 12 32 33
1 2 3
p p
21 23
q q2 q2
q q 0 q q 0
P (2) = P 2 = p 0 q · p 0 q = pq 2pq pq .
0 p p 0 p p p2 p2 p
64 Глава 2. Каналы связи
с дополнительным условием s1 + s2 + s3 = 1:
(q − 1)s1 + qs2 + 0 · s3 = 0
ps1 + (0 − 1)s2 + qs3 = 0
0 · s1 + ps2 + (p − 1)s3 = 0
s1 + s2 + s3 = 1
q2 pq p2
s1 = , s 2 = , s 3 = . N
q 2 + pq + p2 q 2 + pq + p2 q 2 + pq + p2
Решение. Допустим, что в момент времени (t + ∆t) система была свободна. Это
означает, что в предыдущий момент времени t:
или
P0 (t + ∆t) − P0 (t) = −P0 (t)α∆t + P1 (t)β∆t.
Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0
P0 (t + ∆t) − P0 (t)
lim = −P0 (t)α + P1 (t)β
∆t→0 ∆t
Поскольку, по определению производной
Теперь допустим, что в момент времени (t + ∆t) система была занята. Это озна-
чает, что в предыдущий момент времени t:
или
P1 (t + ∆t) − P1 (t) = P0 (t)α∆t − P1 (t)β∆t.
Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0:
0
P1 = αP0 − βP1 .
β α −(β+α)t
p0(t) = + e
β+α β+α
α α −(β+α)t
p1(t) = − e
β+α β+α
Для конкретных значений α = 0.5; β = 0.3 несложно получить и графики зави-
симости состояния системы p0(t) и p1(t) от времени
> a := 0.5; b := 0.3;
p0(t) := b/(a + b) + a ∗ exp((−a − b) ∗ t)/(a + b);
p1(t) := (−a ∗ exp((−a − b) ∗ t) ∗ b/(a + b) + a ∗ b/(a + b))/b;
> plot([p0(t), p1(t)], t = 0..5);
P0( t )
0.5
P1( t )
P2( t )
t
0 2 4 6 8 10
1
P0( t )
0.5
P1( t )
P2( t )
P3( t )
P5( t )
t
0 2 4 6 8 10
68 Глава 2. Каналы связи
Решение.
Обозначим через P0 (t) вероятность того, что микропроцессор свободен (на него
не поступило ни одного прерывания). Тогда P1 (t) - вероятность обработки микро-
процессором одного прерывания, P2 (t) - двух прерываний, P3 (t)-трех прерываний.
Введем обозначения для следующих состояний микропроцессора:
x0 - свободен;
x1 - занят ровно один вход
x2 -занято два входа
x3 -заняты все три входа.
0. Допустим, что в момент времени (t + ∆t) система была свободна. Это означает,
что в предыдущий момент времени t:
или
P0 (t + ∆t) − P0 (t) = −P0 (t)α∆t + P1 (t)β∆t.
Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0
P0 (t + ∆t) − P0 (t)
lim = −P0 (t)α + P1 (t)β
∆t→0 ∆t
Поскольку, по определению производной
P0 (t + ∆t) − P0 (t) dP0 (t)
lim = = P00 ,
∆t→0 ∆t dt
то мы получили дифференциальное уравнение первого порядка
0
P0 = −P0 α + P1 β.
или
P3 (t + ∆t) − P3 (t) = P2 (t)α∆t − 3P3 (t)β∆t.
Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0:
0
P3 = αP2 − 3βP3 .
P0( t )
0.5
P1( t )
P2( t )
t
0 2 4 6 8 10
P0( t )
0.5
P1( t )
P2( t )
t
0 2 4 6 8 10
1
P0( t )
0.5
P1( t )
P2( t )
P3( t )
P5( t )
t
0 2 4 6 8 10
72 Глава 2. Каналы связи
N n α β N n α β N n α β
1 5 0.21 0.36 11 5 0.11 0.31 21 7 0.21 0.19
2 6 0.22 0.37 12 6 0.12 0.32 22 6 0.22 0.20
3 7 0.23 0.38 13 5 0.13 0.33 23 7 0.23 0.21
4 6 0.24 0.39 14 6 0.14 0.34 24 5 0.24 0.22
5 5 0.25 0.40 15 7 0.15 0.35 25 6 0.25 0.23
6 6 0.26 0.41 16 6 0.16 0.49 26 7 0.26 0.24
7 5 0.27 0.42 17 5 0.17 0.50 27 4 0.27 0.25
8 6 0.28 0.43 18 6 0.18 0.21 28 6 0.28 0.46
9 7 0.29 0.44 19 7 0.19 0.33 29 5 0.29 0.47
10 6 0.30 0.45 20 6 0.20 0.34 30 7 0.30 0.48
Система дифференциальных
0 уравнений для данного случая принимает вид
P0 = −αP0 + βP1
0
P 1 = P0 α − (α + β)P1 + 2βP2
0
P2 = P1 α − (α + 2β)P2 + 3βP3
...
0
Pn−1 = Pn−2 α − (α + (n − 1)β)Pn−1 + nβPn
0
Pn = Pn−1 α − (α + nβ)Pn + (nβ + γ)Pn+1
0
Pn+1 = Pn α − (α + nβ + γ)Pn+1 + (nβ + 2γ)Pn+2
0
Pn+2 = Pn+1 α − (α + nβ + 2γ)Pn+2 + (nβ + 3γ)Pn+3
...
0
Pn+k = Pn+k−1α − (nβ + kγ)Pn+k
Начальные условия P0 (0) = 1, P1 (0) = P2 (0) = P3 (0) = P4 (0) = ... = Pn+k (0) = 0.
0 1
P 0 = −P 0 α + P 1 β P0( t )
0
P = P0 α − (α + β)P1 + 2βP2
10
P2 = P1 α − (α + 2β)P2 + 3βP3
0
P3 = P2 α − (α + 3β)P3 + (3β + γ)P4
0
P = P3 α − (α + 3β + γ)P4 + (3β + 2γ)P5 0.5
40
P5 = P4 α − (3β + 2γ)P5 P1( t )
P2( t )
Начальные условия P0 (0) = 1, P3( t )
P1 (0) = P2 (0) = P3 (0) = P4 (0) = P5 (0) = 0. P5( t )
t
0 2 4 6 8 10
Для конкретных значений α = 0.5; β = 0.3; γ = 0.1 график решений принимает
вид, показанный на рисунке.
74 Глава 2. Каналы связи
N n k α β γ N n k α β γ
1 2 1 0.11 0.36 0.21 16 3 3 0.11 0.21 0.36
2 3 2 0.12 0.37 0.22 17 2 1 0.12 0.22 0.37
3 4 3 0.13 0.38 0.23 18 1 2 0.13 0.23 0.38
4 3 2 0.14 0.39 0.24 19 2 2 0.14 0.24 0.39
5 2 1 0.15 0.40 0.25 20 3 1 0.15 0.25 0.40
6 1 2 0.16 0.41 0.26 21 4 2 0.16 0.26 0.41
7 2 3 0.17 0.42 0.27 22 3 4 0.17 0.27 0.42
8 3 2 0.18 0.43 0.28 23 2 3 0.18 0.28 0.43
9 4 1 0.19 0.44 0.29 24 1 3 0.19 0.29 0.44
10 3 2 0.20 0.45 0.30 25 2 1 0.20 0.30 0.45
11 2 3 0.21 0.46 0.31 26 3 2 0.21 0.31 0.46
12 1 2 0.22 0.47 0.32 27 4 4 0.22 0.32 0.47
13 2 1 0.23 0.48 0.33 28 3 1 0.23 0.33 0.48
14 3 3 0.24 0.49 0.34 29 2 3 0.24 0.34 0.49
15 4 2 0.25 0.50 0.35 30 1 4 0.25 0.35 0.50
Стандарт GSM разработан для создания сотовых систем подвижной связи в сле-
дующих полосах частот: 890-915 МГц - для передачи мобильными станциями (теле-
фоном) (линия "вверх"); 935-960 МГц- для передачи базовыми станциями (сотовой
антенной) (линия "вниз").
Каждая из полос, выделенных для сетей GSM, разделяется на частотные каналы.
Разнос каналов составляет 200 кГц, что позволяет организовать в сетях GSM 124 ча-
стотных канала. Частоты, выделенные для передачи сообщений подвижной станцией
на базовую и в обратном направлении, группируются парами, организуя дуплексный
канал с разносом 45 МГц. Эти пары частот сохраняются и при перескоках частоты.
2.4. Стандарт сотовой связи GSM 75
Работа MS
Каждый мобильный телефон имеет кнопку положение трубки, которая может
быть в состоянии трубка поднята и трубка положена. Когда «трубка положена»,
телефон постоянно сканирует либо все каналы системы, либо только управляющие.
Во время набора номера радиотелефон занимает тот свободный канал, уровень сиг-
нала в котором особенно велик. По мере удаления абонента от данной базовой стан-
ции и перемещения его в зону действия другой БС, уровень сигнала падает и каче-
ство разговора ухудшается. Специальная процедура, называемая передачей управ-
ления вызовом или «эстафетной передачей» (в иностранной технической литературе
- handover или handoff), позволяет переключить разговор на свободный канал дру-
гой БС, в зоне действия которой оказался абонент. Для осуществления «эстафетной
передачи» БС снабжена специальным приемником, периодически измеряющим уро-
вень сигнала сотового телефона и сравнивающего его с допустимым пределом. Если
сигнал слишком мал, информация об этом автоматически передается на коммутатор.
ЦКП выдает команду об измерении уровня сигнала на ближайшие к нему базовые
станции. После чего разговор переключается на ту из них, где величина измеренного
сигнала оказалась наибольшей. Все занимает доли секунды. В зависимости от загру-
женности каналов телефон так же может выбирать между сетью 900 и 1800 МГц,
причем переключение возможно даже во время разговора абсолютно незаметно для
говорящего.
Антенна
Базовая станция осуществляет связь с абонентами при помощи приемо-передатчиков
(TRX - transmitter/receiver). 1 базовая станция может обслуживать до 24 приемо-
передатчиков (антенн).
Антенны бывают: 360◦, 120◦, 60◦ , поэтому можно создавать соты с 1 антенной, и
теоретически построить сеть из 24 сот на 1 БС. Ширины диаграммы направленности
антенн в вертикальной плоскости, составляющей обычно менее 10◦ . Часто антенны,
размещенные на мачте, имеют незначительный угол наклона, то есть они слегка опу-
щены вниз таким образом, чтобы специально ограничить радиус действия станций.
Это позволяет, в связи с выше сказанным, неоднократно использовать одни и те же
каналы на других базовых станциях, расположенных на относительно небольшом
расстоянии.
Приемо-передатчик
Мощность излучения приемо-передатчика непостоянна во времени и зависит от
количества абонентов, обслуживаемых БС в данный момент. Максимальная, мощ-
ность на выходе передатчика может составлять около 30 Вт при работе на частоте
1800 МГц и 300 Вт – на частоте 900 МГц, но реально на практике не превышает 5-10
Вт на несущую.
частот колебаний молекул воды. Мощность 650nm ИК лазера DVD - 0.1W. Спут-
никовые передающие антенны, находящиеся на геостационарных орбитах в космосе
на расстоянии 35 тыс. км от Земли, питаются от солнечных батарей, поэтому мощ-
ность передающего сигнала очень невелика - как правило, 150 ватт - и рассеивается
она по огромной площади. Современные наземные ТВ-передатчики в городах имеют
мощность от 100 ватт (в районах) до 25 кВт (в областных центрах).
Мощность излучения сотового телефона меняется от 0.5W до 2W в зависимости
от расстояния до базовой станции. Однако, далее мы увидим, что средняя мощность
телефона в 8 раз меньше установленной, поскольку 7/8 передача не ведется и антена
не излучает.
Кодирование речи
слова, за которыми следуют три бита проверки на четность. Затем биты с нечетны-
ми индексами запоминаются в буферной памяти и переставляются. Далее следуют
четыре нулевых бита, которые необходимы для работы кодера, формирующего код,
исправляющий случайные ошибки в канале. После чего 189 бит класса 1 кодируются
сверточным кодом (2,1,5) со скоростью г=1/2.
Базовая станция (BS) всегда передает на три канальных интервала раньше по-
движного аппарата (HS).
inner code becomes a single erased byte in each of 28 outer code blocks. The outer code
easily corrects this, since it can handle up to 4 such erasures per block.
Свойства кодов Рида-Соломона Коды Рида-Соломона являются субнабором кодов
BCH и представляют собой линейные блочные коды. Код Рида-Соломона специфи-
цируются как RS(n,k) s-битных символов..
Это означает, что кодировщик воспринимает k информационных символов по s
бит каждый и добавляет символы четности для формирования n символьного кодо-
вого слова. Имеется n-k символов четности по s бит каждый. Декодер Рида-Соломона
может корректировать до t символов, которые содержат ошибки в кодовом слове, где
2t = n-k.
Диаграмма, представленная ниже, показывает типовое кодовое слово Рида-Соломона:
Рис. 2. Структура кодового слова R-S
Пример: Популярным кодом Рида-Соломона является RS(255,223) с 8-битными
символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются ин-
формационными и 32 байтами четности. Для этого кода:
n = 255, k = 223, s = 8 2t = 32, t = 16
Декодер может исправить любые 16 символов с ошибками в кодовом слове: то
есть, ошибки могут быть исправлены, если число искаженных байт не превышает 16.
При размере символа s, максимальная длина кодового слова (n) для кода Рида-
Соломона равна n = 2s – 1.
Например, максимальная длина кода с 8-битными символами (s=8) равна 255
байтам.
Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некото-
рого числа информационных символов на входе кодировщика (передавать их в этом
случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив.
Пример: Код (255,223), описанный выше, может быть укорочен до (200,168). Ко-
дировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сфор-
мирует кодовое слово (255,223) и передаст только 168 информационных байт и 32
байта четности.
Объем вычислительной мощности, необходимой для кодирования и декодирова-
ния кодов Рида-Соломона зависит от числа символов четности. Большое значение t
означает, что большее число ошибок может быть исправлено, но это потребует боль-
шей вычислительной мощности по сравнению с вариантом при меньшем t.
Ошибки в символах Одна ошибка в символе происходит, когда 1 бит символа
оказывается неверным или когда все биты не верны.
Пример: Код RS(255,223) может исправить до 16 ошибок в символах. В худшем
случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем
случае, корректируются 16 полностью неверных байт, при этом исправляется 16 x
8=128 битовых ошибок.
Коды Рида-Соломона особенно хорошо подходят для корректировки кластеров
ошибок (когда неверными оказываются большие группы бит кодового слова, следу-
ющие подряд).
Глава 3
Теория помехоустойчивого
кодирования
0 1 2 3 4 5 6 7 8 9 A B C D E F
2 _ ! ” # $ % & ‘ ( ) ∗ + 0
− . /
3 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
4 @ A B C D E F G H I J K L M N O
5 P Q R S T U V W X Y Z [ \ ] ∧ _
0
6 a b c d e f g h i j k l m n o
7 p q r s t u v w x y z { | } ∼ del
8 Ђ Ѓ ѓ „ . . . † ‡ z % Љ < Њ Ќ Ћ Џ
’
9 ђ ‘ ’ “ ” • – — * TM љ > њ ќ ћ џ
A Ў Ў J ¤ Ґ | § Ё c Є « q - r Ї
B ◦
± I i ґ µ ¶ · ё № є » j Ѕ s ї
C A Б В Г Д Е Ж З И Й К Л М Н О П
D Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
E а б в г д е ж з и й к л м н о п
F р с т у ф х ц ч ш щ ъ ы ь э ю я
Из данной таблицы следует, что для передачи одной буквы ее необходимо заме-
нить соответствующей 7-разрядной кодовой комбинацией. Любая 7-разрядная дво-
ичная комбинация представляет собой какой-то знак алфавита и если в процессе
передачи произойдет одна ошибка, то принятая комбинация будет принадлежать
1
ASCII (англ. American Standard Code for Information Interchange) — американский стандарт-
ный код для обмена информацией. ASCII - это кодировка для представления десятичных цифр,
латинского и национального алфавитов, знаков препинания и управляющих символов.
83
84 Глава 3. Теория помехоустойчивого кодирования
другому знаку. Например, если при передаче буквы "m" (6Dh = 11011012) произо-
шла ошибка во 2-м разряде (разряды считаем справа), то мы получим букву "o"
(11011112 = 6Fh ). Если возникающая ошибка просто переводит одну букву алфавита
в другую, то такую ошибку обнаружить не возможно.
Идея помехоустойчивого кодирования заключается в добавлении к сообщению
лишних символов, помогающих заметить ошибку. Теперь множество кодовых комби-
наций увеличивается и состоит из двух подмножеств:
- разрешенных комбинаций и
- запрещенных комбинаций.
Если в результате ошибки исходная комбинация перешла в множество запрещен-
ных, то ошибку можно обнаружить. Однако, возможно, что совокупность ошибок
переведет передаваемую кодовую комбинацию в другую разрешенную. Тогда вместо
одной буквы мы получим другую букву и ошибка не будет обнаружена.
Для того чтобы обнаруживать и исправлять ошибки, разрешенная комбинация
должна как можно больше отличаться от запрещенной. Расстоянием между двумя
комбинациями называется количество разрядов, которыми они отличаются. Напри-
мер расстояние между буквами "m" (1101101) и "o" (1101111) будет 1. Расстояние
между "a" (1100001) и "z" (1111010) будет 4. Весом комбинации называется количе-
ство в ней единиц. Очевидно что вес - это расстояние от нулевой комбинации (00000).
Поскольку сумма комбинаций есть другая комбинация, то по аналогии с векторной
алгеброй можно вычислять расстояние между комбинациями как вес их суммы (по
модулю 2: ⊕).
0101101
⊕
1001010
1100111 расстояние равно 5.
d0 =5
t=2 t=2
010 110
t=1 t=1
d=3
000 111
t=1 t=1
t=1 t=1
001 100 101 011
t=1
2r ≥ k + r + 1.
b0 = a1 ⊕ a2 ⊕ a4 = 1 ⊕ 0 ⊕ 0 = 1
b1 = a1 ⊕ a3 ⊕ a4 = 1 ⊕ 1 ⊕ 0 = 0
b2 = a2 ⊕ a3 ⊕ a4 = 0 ⊕ 1 ⊕ 0 = 1
(b0 , b1 , a1 , b2 , a2 , a3 , a4 ) = (1011010). N
(b0 , b1 , a1 , b2 , a2 , a3 , a4 ) = (1101101).
B0 = a1 ⊕ a2 ⊕ a4 = 0 ⊕ 1 ⊕ 1 = 0
B1 = a1 ⊕ a3 ⊕ a4 = 0 ⊕ 0 ⊕ 1 = 1
B2 = a2 ⊕ a3 ⊕ a4 = 1 ⊕ 0 ⊕ 1 = 0
Отсчитывая слева направо 5-й разряд в комбинации (1101101) и меняя его на про-
тивоположный, получим
(1101101) → (1101001).
Теперь выделяя информационные символы, восстановим сообщение
a1 = 0, a2 = 0, a3 = 0, a4 = 1, или (0001). N
88 Глава 3. Теория помехоустойчивого кодирования
24 ≥ 9 + 4 + 1.
Т.е. нам необходим код [13, 9]. Рассмотрим правила построения [13, 9] кода Хэмминга,
исправляющего одну ошибку в передаваемой информационной комбинации
(a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 ).
(a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 ) = (111001111),
b0 = a1 ⊕ a2 ⊕ a4 ⊕ a5 ⊕ a7 ⊕ a9 = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
b1 = a1 ⊕ a3 ⊕ a4 ⊕ a6 ⊕ a7 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 0
b2 = a2 ⊕ a3 ⊕ a4 ⊕ a8 ⊕ a9 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 0
b3 = a5 ⊕ a6 ⊕ a7 ⊕ a8 ⊕ a9 = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
3.1. Коды Хэмминга 89
(b0 , b1 , a1 , b2 , a2 , a3 , a4 , b3 , a5 , a6 , a7 , a8 , a9 ) = (0010110001111). N
(11011100101)
B0 = a1 ⊕ a2 ⊕ a4 ⊕ a5 ⊕ a7 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1
B1 = a1 ⊕ a3 ⊕ a4 ⊕ a6 ⊕ a7 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0
B2 = a2 ⊕ a3 ⊕ a4 = 1 ⊕ 1 ⊕ 0 = 0
B3 = a5 ⊕ a6 ⊕ a7 = 1 ⊕ 0 ⊕ 1 = 0
90 Глава 3. Теория помехоустойчивого кодирования
Задача 3.1.
Методом Хемминга закодировать информационную последовательность.
N x N x N x
1 111001 11 11111101 21 1011010011
2 101101 12 11111011 22 1101001111
3 101111 13 11110111 23 1000111111
4 110111 14 11101111 24 1111011001
5 111011 15 11011111 25 1111101101
6 111101 16 10111111 26 1110010111
7 111110 17 10011111 27 1001111011
8 100111 18 11001111 28 1111100101
9 110011 19 11100111 29 1110011110
10 111001 20 11110011 30 1001111111
Задача 3.2.
На приемнике было получено кодовое слово x сформированное кодом Хемминга.
Восстановить исходное сообщение.
N x N x N x
1 1110001 11 0101001 21 1001001
2 0111010 12 1101010 22 0001010
3 1010011 13 0100011 23 1100011
4 1011100 14 0001100 24 1101100
5 0100001 15 1101110 25 0011111
6 0100111 16 1110110 26 0100111
7 0100100 17 1000110 27 0001011
8 1100111 18 0100110 28 0001101
9 1100100 19 1001111 29 0001110
10 1100010 20 0101111 30 1110010
92 Глава 3. Теория помехоустойчивого кодирования
N x N x N x
1 1110011100 11 001001001111 21 00100101101001
2 1011010100 12 111001001111 22 11100101101001
3 1011111010 13 100001001111 23 10000101101001
4 1101110101 14 101101001111 24 10110101101001
5 1110010011 15 101011001111 25 10101101101001
6 1110100011 16 111000011011 26 10000001011001
7 1110111011 17 111001111011 27 10000111011001
8 1110110111 18 111001001011 28 10000100011001
9 1110110001 19 111001010011 29 10000101111001
10 1110110010 20 111001011111 30 10000101001001
N x N x
1 00101010111110111011 16 10001000111110101111011
2 11101010111110111011 17 10001000111110110111011
3 10001010111110111011 18 10001000111110111011011
4 10111010111110111011 19 10001000111110111111111
5 10100010111110111011 20 10001000111110110111011
6 101011001111101111111 21 0000111111111010111101101
7 101010101111101111111 22 1100111111111010111101101
8 101010011111101111111 23 1010111111111010111101101
9 101010000111101111111 24 1001111111111010111101101
10 101010001011101111111 25 1000011111111010111101101
11 1000100011011011111101 26 1000101111111010111101101
12 1000100011101011111101 27 1000110111111010111101101
13 1000100011110011111101 28 1000111011111010111101101
14 1000100011111111111101 29 1000111101111010111101101
15 1000100011111001111101 30 1000111110111010111101101
3.2. Циклические коды 93
k
X
n−1 n−2 2
u(x) = a1 x + a2 x + ... + an−2 x + an−1 x + an = ai xk−1 .
i=1
В поле Галуа GF (2) (Galous Field) коэффициенты при степенях x могут прини-
мать значения только 0 или 1, тогда
1 − x − x2 = 1 + x + x2 ,
5 + 2x + 3x2 = 1 + 0x + x2 = 1 + x2 .
x2 + 1 = (1 + x)2 ,
x3 + 1 = (1 + x)(1 + x + x2 ),
x4 + 1 = (1 + x)4 ,
x5 + 1 = (1 + x)(1 + x + x2 + x3 + x4 ),
x6 + 1 = (1 + x)2 (1 + x + x2 )2 .
2
БЧХ (Bose-Chadhuri-Hocquenghem) коды являются классом циклических кодов
94 Глава 3. Теория помехоустойчивого кодирования
h i
P (x)
Обозначим остаток R(x) от деления полинома P (x) на полином Q(x) через Q(x)
,
тогда
P (x) R(x) P (x)
= C(x) + т.е. = R(x).
Q(x) Q(x) Q(x)
Двоичную последовательность, соответствующую полиному остатков запишем в
десятичном виде. Например
x2 x3
2
= x = 100 = 4, = x + 1 = 011 = 3.
x3 + x2 + 1 x3 + x + 1
h nn i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
x
p(x)
1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 1 2
ord p(x) = T.
x ord = 1
n = 1.
x + 1 − не примитивный ord = 0
n = 2. x2 + x + 1 ord = 3
x3 + x + 1 ord = 7
n = 3.
x3 + x2 + 1 ord = 7
x4 + x + 1 ord = 15
n = 4. x4 + x3 + 1 ord = 15
x4 + x3 + x2 + x + 1 − не примитивный ord = 5
F µ1 =1
F µ2 = (−)1 = −1
F µ3 = (−)1 = −1
F µ4 = µ22 = 0
F µ5 = (−)1 = −1
F µ6 = µ2·3 = (−)2 = 1
F µ7 = (−)1 = −1
F µ8 = µ22 ·2 = 0
Формула Количество неприводимых полиномов степени n определяется
Мебиуса с помощью выражения
n
1 X
In = µk 2n/k
n
k=1,(k|n)
r P (x)
2
2 x +x+1 111
x3 + x + 1 1011
3
x3 + x2 + 1 1101
x4 + x + 1 10011
4
x4 + x3 + 1 11001
x5 + x2 + 1 100101
5 x5 + x4 + x3 + x2 + 1 111101
x5 + x4 + x2 + x + 1 110111
x6 + x + 1 1000011
6
x6 + x5 + x2 + x + 1 1100111
x7 + x3 + 1 10001001
7 x7 + x3 + x2 + x + 1 10001111
x7 + x4 + x3 + x + 1 10011101
x + x7 + x6 + x5 + x2 + x + 1
8
111100111
8 x8 + x4 + x3 + x2 + 1 100011101
x8 + x6 + x5 + x + 1 101100011
x9 + x5 + x3 + x2 + 1 1000101101
9
x9 + x8 + x7 + x6 + x5 + x3 + 1 1111101001
x10 + x4 + x3 + x + 1 10000011011
10
x10 + x9 + x6 + x5 + x4 + x3 + x2 + x + 1 11001111111
x11 + x10 + x9 + x8 + x3 + x + 1 111100001011
11
x11 + x8 + x6 + x2 + 1 100101000101
x12 + x11 + x9 + x8 + x7 + x5 + x2 + x + 1 1101110100111
12
x12 + x9 + x3 + x2 + 1 1001000001101
Если информационную последовательность представить в виде полинома Q(x),
то передаваемая комбинация F имеет вид
F = P C,
где полином C необходимо найти из выражения
xr Q R
=C+ .
P P
Если в передаваемой комбинации возникает ошибка, то ее обнаруживают сравнением
k
остатков от деления FP и xP .
3.2. Циклические коды 97
Пример 3.6. Рассмотрим построение повторного кода [n, k] = [3, 1]. Предста-
вим информационную последовательность в виде Q(x) = e, где e ∈ GF2 ; (e = 0, 1).
Образующий полином имеет вид
P (x) = x2 + x + 1.
Поскольку r = 2, то умножим
x2 Q(x) = ex2
и найдем
x2 Q(x) = C(x) · P (x) + R(x) = e · (x2 + x + 1) + ex + e.
Передаваемая последовательность имеет вид
x2
1 x
= 1 = (01); = x = (10); = x + 1 = (11).
P (x) P (x) P (x)
Пример 3.7. Рассмотрим построение полиномиального кода [n, k] = [7, 4]. Для
передачи информационной последовательности 0111 нам необходимо иметь дополни-
тельно r = 3 проверочных символа. Информационная последовательность a = (0111)
представляется в виде
Q(x) = x3 · 0 + x2 · 1 + x · 1 + 1 · 1 = x2 + x + 1.
Поскольку r = 3, то умножаем
P (x) = x3 + x + 1
3
Синдром - совокупность признаков характеризующих заболевание. Медицинский термин ис-
пользуемый в теории информации при построении корректирующих кодов. В данном случае син-
дром - это совокупность признаков характеризующих ошибку в передаваемой кодовой комбинации.
98 Глава 3. Теория помехоустойчивого кодирования
x3 Q R x5 + x4 + x3 2 2x2 + x
=C+ или = (x + x) −
P P x3 + x + 1 x3 + x + 1
окуда получим R = 2x2 + x. Аналогичный результат можно получить в Mathcad:
остаток от деления полиномов определяется оператором parfrac в панели Symbolic:
x5 + x4 + x3 2x + 1
3
convert, parfrac, x → x + x2 − x · 3 .
x +x+1 x +x+1
В любом случае остаток
R(x) = −(2x2 + x)
необходимо привести по модулю 2. Поскольку в этом случае 2 = 1 ⊕ 1 = 0 и −1 = +1,
получим
R(x) = −(2x2 + x) = (2x2 + x) = 0 · x2 + x = x = 010.
Поскольку
m(x) = x5 + x4 + x3 = 0111000
то передаваемая комбинация F есть прямая конкатенация m ⊕ R:
m = 0111000
R= 010
F = 0111010
F = (0111010) → F = (0101010)
2r ≥ n + 1
F
Найдем остаток от деления P
F
R(x) = = x − x2 = x + x2 = 0110
P
Заметим, что далее остатки повторяются. Место ошибки определяется степенью зна-
менателя синдрома, совпадающего с остатком [ PF ]. В данном случае остаток 0110
соответствует синдрому с x4 , поэтому необходимо исправить ошибку в 4 степени
передаваемой последовательности
0101010 ⇒ 0111010.
Задача 3.5.
Построить полиномиальный код для следующей информационной последователь-
ности.
N x N x N x
1 110010011 11 10011010111 21 00110001110
2 111001 12 010100111111 22 11111001001
3 1011101 13 1101111010 23 0001011110
4 1100001011 14 01011010111 24 1110110100010
5 10100111 15 11000011 25 110001101011
6 10111010 16 100011 26 11011001010101
7 10001101 17 11010 27 11111010101011
8 100111111 18 111011010 28 1110101010111
9 1001000101 19 100011110 29 101010101011
10 1100100111 20 01000110 30 00011010110101001
N x N x N x N x N x
1 1100110 7 0011111 13 1010011 19 0110011 25 1101011
2 1101000 8 0110001 14 1111111 20 1001010 26 0011011
3 1000100 9 0000110 15 0111101 21 1111010 27 1001111
4 0110011 10 1001110 16 0110110 22 0100101 28 1010011
5 0010101 11 1101110 17 1011100 23 0100010 29 0110110
6 0100100 12 1110101 18 1011110 24 1001000 30 0110011
N x N x N x N x N x
1 001001001 7 001101111 13 101110111 19 101011111 25 001011011
2 011011111 8 111001001 14 111101111 20 101011111 26 011110111
3 110110111 9 001111111 15 100001001 21 100101111 27 001001111
4 101001111 10 111010111 16 001011101 22 101011001 28 001011110
5 111111100 11 101111111 17 111111111 23 000011111 29 101000001
6 101011111 12 101001011 18 101100111 24 111110011 30 001011101
3.2. Циклические коды 101
N x N x
1 10111111111111100111 16 11001111111111101001
2 11111111111111100001 17 11000011111111101011
3 11011111111111100111 18 11111101111111100111
4 00111111111111100001 19 00000011111111101011
5 00001111111111101001 20 11101111111111100111
6 01100011111111101011 21 01011111111111100001
7 11110111111111100111 22 01101111111111101001
8 01101111111111100001 23 01010011111111101011
9 01000111111111101001 24 11111011111111100111
10 01001011111111101011 25 01110111111111100001
11 11111101111111100111 26 01001011111111101001
12 01111110111111100001 27 01000111111111101011
13 01001101111111101001 28 11111110111111100111
14 01000001111111101011 29 01111111111110100001
15 11111111101111100111 30 01001110111111101001
102 Глава 3. Теория помехоустойчивого кодирования
n = k + r1 + r2
n(n + 1)
2r1 +r2 ≥ Cn0 + Cn1 + Cn2 = 1 +
2
ошибок. Однако, порядок произведения полиномов pr (x) степени r, вычисляется по
формуле
ord (pr · pm ) = НОК(ord pr , ord pm )
если полиномы разного порядка (степени), и
n(n + 1)
ord (pr1 · pr2 ) ≥ 1 + .
2
(a) → (aaaaa).
ord (pr · pr ) = 2ord (pr ) или ord (p3 · p3 ) = 2ord (p3 ) = 2 · 7 = 14.
C81 + C82 = 8 + 32 = 40
ошибок.
F Увеличим степени полиномов: p3 = x3 + x + 1 и p4 = x4 + x + 1, тогда
ord (pr · pm ) = НОК(ord pr , ord pm ) или ord (p3 · p4 ) = НОК(7, 15) = 7 · 15 = 105.
C91 + C92 = 9 + 36 = 45
x7 Q(x)
= 1 + x + x2 + x4 + x5 + x6 ,
(1 + x2 + x3 )(1 + x3 + x4 )
или
R(x) = 1 + x + x2 + x4 + x5 + x6 = (001110111)
104 Глава 3. Теория помехоустойчивого кодирования
100000000
⊕
001011010
101011010
или
F = x + x3 + x4 + x6 + x8 .
Допустим в кодовой последовательности возникло 2 ошибки, после чего она при-
няля вид
F = (111011110) = x + x2 + x3 + x4 + x6 + x7 + x8 .
F
Найдем остаток от деления P
F
R(x) = = 1 + x3 + x5 = 0101001
P
k xk 1 + xk x + xk x2 + xk x3 + xk x4 + xk x5 + xk x6 + xk
0 0000001
1 0000010 0000011
2 0000100 0000101 0000110
3 0001000 0001001 0001010 0001100
4 0010000 0010001 0010010 0010100 0011000
5 0100000 0100001 0100010 0100100 0101000 0110000
6 1000000 1000001 1000010 1000100 1001000 1010000 1100000
7 0101101 0101100 0101111 0101001 0100101 0111101 0001101 1001101
8 1101010 1011011 1011000 1011110 1010010 1001010 1111010 0111010
h i
x7 +x8
Здесь необходимо добавить P
= 1 + x + x2 + x4 + x6 = 1010111.
Пользуясь таблицей находим, что остаток R = 0101001 соответствует остатку x2 + x7 ,
т.е. ошибкам во 2 и 7 разряде полинома кодовой комбинации. Исправляя, получим
111011110 ⇒ 101011010.
N x N x N x
1 010101000 11 101010011 21 111100110
2 010100111 12 101001000 22 111010101
3 010111001 13 101111110 23 110110011
4 010000101 14 100010010 24 101111111
5 011111101 15 111001010 25 011100111
6 000001101 16 001111010 26 111010110
7 111101101 17 100011011 27 110110101
8 000101100 18 111011000 28 101110011
9 110101111 19 001011110 29 011111111
10 010100100 20 101010011 30 111100110
N x N x N x
1 1010101000 11 100101010011 21 1001111100110
2 0010100111 12 101101001000 22 1000111010101
3 00010111001 13 110101111110 23 0111110110011
4 01010000101 14 11100010010 24 0110101111111
5 10011111101 15 1111111001010 25 0101011100111
6 11000001101 16 1110001111010 26 0100111010110
7 000111101101 17 1101100011011 27 0011110110101
8 001000101100 18 1100111011000 28 0010101110011
9 010110101111 19 1011001011110 29 0001011111111
10 011010100100 20 1010101010011 30 0000111100110
106 Глава 3. Теория помехоустойчивого кодирования
а считывается по столбцам (a11 a21 a31 ...ak2 ). В результате исходные символы, которые
следовали друг за другом, передаются в канал с интервалом в k символом, который
называется глубиной перемежения.
Если матрица квадратная, то процесс декодирования аналогичен предыдущему
алгоритму. Если же матрица прямоугольная то декодирование производится в об-
ратном порядке: последовательность записывается по столбцам, а считывается по-
строчно.
Например возьмем сообщение выстрел и закодируем его повторным кодом [n, k] =
[3, 1]. Получим кодовую комбинацию вввыыыссстттррреееллл. Допустим во вре-
мя передачи этого сообщения оно было искажено пакетной ошибкой, т.е. заменим
последовательно 5 символов начиная с 8-го на букву а вввыыысаааааррреееллл.
Если попытаться раскодировать это сообщение как есть, то мы получим ввв ыыы
саа ааа ррр еее ллл ⇒ выаарел.
Теперь перед отправлением сообщения используем метод перемежения. Для этого
3.3. Сверточные коды 107
в в в ы ы
ы с с с т
т т р р р
е е е л л
л _ _ _
в в а ы ы
ы с а с т
т а р р р
е а е л л
л а _ _
и прочитаем построчно вва ыыы сас тта ррр еае ллл а__ ⇒ выстрел. Как
видно сообщение без труда восстанавливается в правильном виде.
f g
0 1 0 1
s0 s1 s0 0 1
s1 s1 s2 1 1
s2 s0 s1 1 0
Решение.
1 метод. Исследование работы автомата удобнее проводить в два этапа. На пер-
вом этапе мы рассмотрим изменение состояния автомата под действием входного
сигнала (т.е. функцию f ).
Запишем в строку значения входного сигнала
a = (0011101010).
Начальное состояние автомата s0 запишем над первым значением. Первое значе-
ние входного сигнала a1 = 0. По таблице для f на пересечении s0 и 0 находим новое
состояние автомата s1 и запишем его над вторым значением сигнала:
s0 −→ s1
0 %
Второе значение входного сигнала a2 = 0. По таблице для f на пересечении s1 и 0
находим новое состояние автомата s1 и запишем его над третьим значением сигнала:
s0 −→ s1 −→ s1
0 % 0 %
Третье значение входного сигнала a3 = 1. По таблице для f на пересечении s1 и
1 находим новое состояние автомата s2 и запишем его над четвертым значением
сигнала:
s0 −→ s1 −→ s1 −→ s2
0 % 0 % 1 %
и т.д.
Полная последовательность состояний, принимаемых автоматом под воздействи-
ем входного сигнала имеет вид
sk s0 → s1 → s1 → s2 → s1 → s2 → s0 → s0 → s1 → s2
a 0 % 0 % 1 % 1 % 1 % 0 % 1 % 0 % 1 % 0
Теперь, зная все состояния автомата найдем выходной сигнал используя функцию
g таблицы. Для первого значения входного сигнала a1 = 0 и состояния s0 найдем
выходное значение 0:
s0
0
0
3.3. Сверточные коды 109
s2 s1
1/1
0/1
0 0 1 1 1 0 1 0 1 0
s0 s0 s0 s0 s0 s0 s0 s0 s0 s0 s0
1/1
0/0 0/0
0/1 0/1
0/1
s1 s1 s1 s1 s1 s1 s1 s1 s1 s1 s1
1/1 1/1 1/1
1/0
s2 s2 s2 s2 s2 s2 s2 s2 s2 s2 s2
0 1 1 0 1 1 1 0 1 1
z = (0110111011). N
Задача 3.11. На вход автомата подается ASCII код первой буквы фамилии
курсанта. Получить выходной сигнал, если функции перехода f и g автомата заданы
таблицей. Начертить граф автомата.
01 f g 02 f g 03 f g 04 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s0 s2 0 1 s0 s1 s2 0 1 s0 s1 s3 0 1 s0 s1 s2 0 1
s1 s1 s3 1 1 s1 s1 s3 0 1 s1 s1 s2 1 1 s1 s1 s2 1 1
s2 s0 s2 1 1 s2 s3 s1 1 1 s2 s2 s1 0 1 s2 s1 s2 1 1
s3 s1 s3 1 1 s3 s2 s1 1 1 s3 s3 s1 1 1 s3 s1 s2 0 1
05 f g 06 f g 07 f g 08 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s0 s2 0 1 s0 s0 s2 0 1 s0 s1 s3 0 1 s0 s1 s2 0 1
s1 s0 s2 1 1 s1 s1 s3 1 1 s1 s2 s0 1 1 s1 s2 s3 1 0
s2 s0 s2 1 1 s2 s2 s0 1 0 s2 s3 s1 1 1 s2 s3 s0 1 1
s3 s0 s2 1 1 s3 s3 s1 1 1 s3 s0 s2 1 0 s3 s0 s1 1 1
09 f g 10 f g 11 f g 12 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s3 s1 0 0 s0 s1 s2 0 1 s0 s1 s2 1 1 s0 s1 s0 0 1
s1 s0 s2 1 1 s1 s1 s2 0 1 s1 s1 s0 0 1 s1 s1 s2 1 1
s2 s0 s2 1 1 s2 s0 s1 1 0 s2 s2 s1 0 0 s2 s0 s2 1 0
s3 s3 s1 1 1 s3 s1 s1 1 0 s3 s0 s1 1 0 s3 s0 s2 0 0
13 f g 14 f g 15 f g 16 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s1 s0 1 1 s0 s1 s2 1 1 s0 s1 s2 0 1 s0 s1 s3 0 1
s1 s1 s0 0 1 s1 s1 s2 1 1 s1 s1 s2 0 0 s1 s2 s3 1 0
s2 s0 s1 1 0 s2 s0 s1 0 0 s2 s3 s1 1 1 s2 s3 s1 0 1
s3 s0 s1 0 0 s3 s0 s1 0 0 s3 s3 s1 1 0 s3 s0 s1 1 0
17 f g 18 f g 19 f g 20 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s1 s2 1 1 s0 s1 s0 0 1 s0 s0 s0 1 1 s0 s0 s3 1 1
s1 s2 s2 0 0 s1 s2 s3 1 0 s1 s1 s1 0 0 s1 s3 s1 1 0
s2 s3 s1 0 1 s2 s3 s2 1 1 s2 s2 s2 1 1 s2 s2 s2 0 1
s3 s0 s1 1 0 s3 s0 s1 0 0 s3 s3 s3 0 0 s3 s1 s0 0 0
21 f g 22 f g 23 f g 24 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s1 s0 0 1 s0 s1 s0 0 1 s0 s1 s0 1 1 s0 s0 s0 0 1
s1 s2 s0 0 0 s1 s2 s0 1 0 s1 s2 s0 0 0 s1 s1 s3 1 0
s2 s3 s1 1 0 s2 s3 s2 0 0 s2 s3 s3 0 0 s2 s2 s0 1 0
s3 s3 s1 1 1 s3 s3 s2 1 1 s3 s3 s3 1 1 s3 s3 s3 0 1
112 Глава 3. Теория помехоустойчивого кодирования
25 f g 26 f g 27 f g 28 f g
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
s0 s0 s2 1 1 s0 s0 s1 1 1 s0 s0 s1 0 0 s0 s0 s0 0 0
s1 s1 s3 0 0 s1 s1 s2 1 0 s1 s1 s2 0 1 s1 s1 s0 1 1
s2 s2 s0 1 0 s2 s2 s3 0 0 s2 s2 s1 1 0 s2 s2 s0 0 0
s3 s3 s1 0 1 s3 s3 s0 0 1 s3 s3 s2 1 1 s3 s3 s0 1 1
f g
0 1 0 1 0/00
s0 s0 s2 00 11
s1 s0 s2 11 00
s2 s1 s3 10 01 0/11 s0 1/11
s3 s1 s3 01 10
1/00
Пример 3.14. Согласно таблице перехо- s1 s2
да для входной последовательности
0/10
a = (1, 1, 0, 1, 1, 0, 1, 1) 0/01 1/01
s3
автомат выдаст сигнал
1/10
F = (11, 01, 01, 00, 01, 10, 01, 11). N
t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 t=10 t=11
s0
s1
s2
s3
F= 00 11 10 11 11 10 00 01 10 01 11
114 Глава 3. Теория помехоустойчивого кодирования
Допустим в передаваемой комбинации возникла ошибка F (x) = (11, 11, 00, 10).
Необходимо восстановить информационную последовательность.
3.3. Сверточные коды 115
На втором шаге из узла s2 (t=1) треллиса мы должны вы- t=0 t=1 t=2
брать ребро с весом 11, соответствующим второй паре по- s0
лученной кодовой комбинации F (x). Так как ребер с таким
весом у нас нет, то мы рассмотрим оба имеющихся вариан- s1 10 1
та. Для верхнего ребра имеем вес 10. Запишем расстояние s2 01
между 10 и 11 в узел s1 (t=2). Для нижнего ребра имеем s3 1
вес 01. Расстояние между 01 и 11 равно 1 - запишем в узел F= 11 11
s3 (t=2).
t=0 t=1 t=2 t=3 Третья пара принятой комбинации имеет зна-
s0 чение 00. На третьем шаге мы имеем два марш-
2
11
11 рута. Из узла s1 (t=2) треллиса выходят 2 реб-
s1 1 1 ра с весом 11 и 00. Расстояния между ними и
10 00
s2 0 принятым значением запишем в соответствую-
01 01
s3 1 10 1 щих узлах: 2-для s0 и 0-для s2 . Из узла s3 также
F= 11 11 00 выходят два ребра с весом 01 и 10. Расстояние
между ними и принятым знчением 00 равно 1
записывается в узлы s1 и s3 (t=3).
t=0 t=1 t=2 t=3 t=4 На 4 шаге нам необходимо отбросить узлы
s0 с максимальным весом, поскольку они со-
ответствуют последовательностям наибо-
s1 0 лее сильно отличающимся от передавае-
10
s2 мой. Для дальнейшего пути мы оставля-
s3 ем только узел s2 . Четвертая пара приня-
F= 11 11 00 10 той комбинации имеет значение 10. Из уз-
ла s2 (t=3) треллиса выходит верхнее реб-
ро с весом 10 и мы переходим по этому
ребру в узел s1 .
116 Глава 3. Теория помехоустойчивого кодирования
a = (111000101).
t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9
00
s0 11
11
s1 11
10 00
01
s2 01
10
s3
a = 1 1 1 0 0 0 1 0 1
F= 11 01 10 01 11 00 11 10 00
Вторая пара пара принятой комбинации имеет значение t=0 t=1 t=2
01. Нам необходимо продолжить уже два маршрута. Из s0 00 1 00 1
узла s0 (t=1) треллиса выходят 2 ребра с весом 11 и 00. Рас- s1 11
11
2
стояния между ними и принятым значением 01 запишем 10
s2 1 1
в соответствующих узлах: 2-для s0 и 0-для s2 . Из узла s2 01
также выходят два ребра с весом 01 и 10. Расстояние меж- s3 0
01 01
ду ними и принятым знчением 00 равное 1 записывается
в узлы s1 и s3 (t=2).
t=0 t=1 t=2 t=3 На третьем шаге из узла s3 (t=2) мы должны выбрать
s0 ребро с весом 11. Так как ребер с таким весом у нас нет,
s1 1 то мы рассмотрим маршруты по ребрам с весом 01 и 10.
s2 Запишем расстояние между 01 и 11 в узел s1 (t=3). Для
01
нижнего ребра имеем вес 10. Расстояние между 10 и 11
s3 10 1
равно 1 - запишем в узел s3 (t=3).
01 01 11
Следующая пара принятой комбинации имеет t=0 t=1 t=2 t=3 t=4
значение 01. Нам необходимо продолжить уже s0 1
два маршрута. Из узла s1 (t=3) выходят 2 ребра s1 1
11
0
00
с весом 11 и 00. Расстояния между ними и при-
s2 01 1
нятым значением 01 запишем в соответствую- 01
щих узлах: 1-для s0 и s2 . Из узла s3 также вы- s3 10 1 10 2
01 01 11 01
ходят два ребра с весами 01 и 10. Расстояние
между ними и принятым значением 01 записы-
вается в узелы s1 (0) и s3 (2).
t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9
10
0
01 01 11 01 10 00 10 10 10
Решение. Для обнаружения такой t=0 t=1 t=2 t=3 t=4 t=5 t=6
ошибки нам необходимо начертить s0 2 0 0 0 0 0
треллис глубиной до шестого уровня s1 1 1 1
включительно. И только на 6 уровне
сумма расстояний по верхнему пу- s2 0 0 0
Таким образом исходное кодовое слово имеет вид F = (11, 10, 00, 00, 11, 11, 11, 11).
Для раскодирования сообщения воспользуемся треллисом
3.4. Алгоритм Витерби 121
a = (10100110)2 = a6h = | . N
F = (110110011100).
dB dB
t t
1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0
dB
F = (111110011101) t
т.е. с двумя ошибками. 1 1 1 1 1 0 0 1 1 1 0 1
s0 0 0
0
s1 1 1
0 1
s2 0 0
1
s3 1
1 1 1 0 0 0
3.5 Турбокоды
Турбокоды были введены в практику в 1993 г. и по существу являются комбинацией
двух сверточных кодов. Они обеспечивают значения достоверности очень близкое к
пределу Шеннона.
Турбокоды в настоящее время приняты в качестве стандарта для систем связи
телекоммуникаций третьего поколения 3GPP, стандарта сотовой связи CDMA-2000,
цифрового телевидения DVB, используются в системах спутниковой связи VSAT и
во многих др. стандартах.
Как и в случае мягкого декодирования Витерби, логические элементы 0 и 1 мы
будем представлять электрическим напряжением (-1) и (+1). Проверочные символы
для информационной последовательности a = (x1 , x2 , x3 , x4 ) строятся следующим
образом. Представим последовательность xk в виде матрицы
L1 L2 x1 x2 x12
L= = ,
L3 L4 x3 x4 x34
( x13 x24 )
X 1 = L + H + V.
130 Глава 3. Теория помехоустойчивого кодирования
dB dB
1 0 1 1 t 1 0 1 1 1 0 0 1 t
dB
F = (00111000)
dB
0,9
0,7
0,5
0,3
0,1
F = (x1 , x2 , x3 , x4 , x12 , x34 , x13 , x24 ) = (0.4, 0.5, 0.8, 0.9, 0.7, 0.3, 0.3, 0.5)
информационную матрицу
x1 x2 0.4 0.5
L= = ,
x3 x4 0.8 0.9
Учитывая, что
A B = (−1) · sign(A) · sign(B) · min(|A|, |B|)
3.5. Турбокоды 133
получим
и
H1 H2 −0.5 −0.4
H= = .
H3 H4 −0.3 −0.3
2. На втором шаге вычисляем вертикальную невязку проверочных символов
(L3 + H3 ) x13 (L4 + H4 ) x24 (0.8 − 0.3) 0.3 (0.9 − 0.3) 0.5
V = = .
(L1 + H1 ) x13 (L2 + H2 ) x24 (0.4 − 0.5) 0.3 (0.5 − 0.4) 0.5
или
V1 V2 −0.3 −0.5
V = = .
V3 V4 0.1 −0.1
Результатом первой итерации является матрица
0.4 0.5 −0.5 −0.4 −0.3 −0.5 −0.4 −0.4
X1 = L+H+V = + + = .
0.8 0.9 −0.3 −0.3 0.1 −0.1 0.6 0.5
a = (1011). N
N F N F
1 0.9, 0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 16 0.8, 0.1, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
2 0.9, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 17 0.8, 0.2, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
3 0.9, 0.3, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 18 0.8, 0.3, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
4 0.9, 0.4, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 19 0.8, 0.4, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
5 0.9, 0.5, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 20 0.8, 0.5, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
6 0.9, 0.6, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 21 0.8, 0.6, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
7 0.9, 0.7, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 22 0.8, 0.7, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
8 0.9, 0.1, 0.1, 0.4, 0.5, 0.6, 0.7, 0.8 23 0.8, 0.8, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
9 0.8, 0.1, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 24 0.8, 0.9, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7
10 0.8, 0.2, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 25 0.8, 0.9, 0.5, 0.8, 0.4, 0.9, 0.5, 0.6
11 0.8, 0.3, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 26 0.8, 0.9, 0.4, 0.8, 0.4, 0.9, 0.5, 0.6
12 0.8, 0.4, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 27 0.8, 0.9, 0.3, 0.8, 0.4, 0.9, 0.5, 0.6
13 0.8, 0.5, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 28 0.8, 0.9, 0.2, 0.8, 0.4, 0.9, 0.5, 0.6
14 0.8, 0.6, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 29 0.8, 0.9, 0.1, 0.8, 0.4, 0.9, 0.5, 0.6
15 0.8, 0.7, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 30 0.7, 0.8, 0.4, 0.8, 0.4, 0.7, 0.5, 0.7
3.6. Вычисления в полях Галуа 135
Если занятия начались в 11 часов и будут длится 2 часа, то во сколько они закон-
чатся? Обычно ответ вычисляется следующим образом
11 + 2 = 13,
13 − 12 = 1
10 + 9 = 19 ≡ 19 − 12 = 7
20 + 6 · 24 + 15 = 179.
179 11
= 14 +
12 12
или
179 = 14 · 12 + 11.
Т.е. поезд прибудет во Владивосток в 11 часов. (Мы пока не обсуждаем вопрос: но-
чью или днем?) Т.е. для определения данного времени нам понадобилось вычислить
остаток от деления 179 на 12. Этот остаток и является ответом. Математически,
данный факт записывается так
+ 0 1 2 × 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1
1 · 1 = 1, 2 · 3 = 1, 3 · 2 = 1, 4 · 4 = 1.
Т.е. для 2 обратным элементом будет 3, для 3 - это 2, для 1 - это 1, а для 4 - это 4.
Получается что в кольце Z5 элементы (0,1,2,3,4) образуют группу как по сложению
так и по умножению.
Полем называется множество элементов, с двумя бинарными операциями ("+"и
” × ”), которое является группой как по сложению, так и по умножению (т.е. адди-
тивной и мультипликативной группой одновременно).
Несложно проверить что все кольца Zp , для которых p является простым числом
являются конечными полями.
Для составления таблиц умножения в конечных полях и проведения в них ариф-
метических операций часто пользуются таблицами индексов. Таблица индексов для
Z7 строиться следующим образом. Возьмем произвольное число (например 2) и будем
искать остатки при делении его степени 2n на 7:
2n (mod 7) = (1, 2, 4)
138 Глава 3. Теория помехоустойчивого кодирования
n 0 1 2 3 4 5 6
3n 1 3 2 6 4 5 1
n 0 1 2 3 4 5 6
ind n 6 0 2 1 4 5 3
+ 0 1 2 3 4 5 6 × 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0
1 1 2 3 4 5 6 0 1 0 1 2 3 4 5 6
2 2 3 4 5 6 0 1 2 0 2 4 6 1 3 5
3 3 4 5 6 0 1 2 3 0 3 6 2 5 1 4
4 4 5 6 0 1 2 3 4 0 4 1 5 2 6 3
5 5 6 0 1 2 3 4 5 0 5 3 1 6 4 2
6 6 0 1 2 3 4 5 6 0 6 5 4 3 2 1
F Аналогичным образом построим поле Галуа GF (24). Для этого возьмем непри-
водимый полином 4 степени с коэффициентами из Z2 :
p(x) = x4 + x + 1
0001 = 1, 0010 = 2, 0011 = 3, ..., 1101 = 13, 1110 = 14, 1111 = 15,
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2n 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 1
ind n 15 0 1 4 2 8 5 10 3 14 9 7 6 13 11 12
Теперь, пользуясь таблицей индексов несложно построить таблицу умножения
для GF (24 ):
× 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 2 4 6 8 10 12 14 3 1 7 5 11 9 15 13
3 3 6 5 12 15 10 9 11 8 13 14 7 4 1 2
4 4 8 12 3 7 11 15 6 2 14 10 5 1 13 9
5 5 10 15 7 2 13 8 14 11 4 1 9 12 3 6
6 6 12 10 11 13 7 1 5 3 9 15 14 8 2 4
7 7 14 9 15 8 1 6 13 10 3 4 2 5 12 11
8 8 3 11 6 14 5 13 12 4 15 7 10 2 9 1
9 9 1 8 2 11 3 10 4 13 5 12 6 15 7 14
10 10 7 13 14 4 9 3 15 5 8 2 1 11 6 12
11 11 5 14 10 1 15 4 7 12 2 9 13 6 8 3
12 12 11 7 5 9 14 2 10 6 1 13 15 3 4 8
13 13 9 4 1 12 8 5 2 15 11 6 3 14 10 7
14 14 15 1 13 3 2 12 9 7 6 8 4 10 11 5
15 15 13 2 9 6 4 11 1 14 12 3 8 7 5 10
Сложение определяется как побитовая сумма по модулю 2 оператором XOR. В об-
щем случае показанная схема позволяет для любого pk построить поле GF (pk ).
3.7. Коды БЧХ 141
По формуле
q
X
2r ≥ i
Ck+r
i=0
Например
F GF (22 ) :
x3 − 1 = (1 + x)(1 + x + x2 )
F GF (23 ) :
x7 − 1 = (1 + x)(1 + x + x3 )(1 + x2 + x3 )
F GF (24 ) :
F GF (25) :
x31 − 1 = (1 + x)(1 + x2 + x5 )(1 + x3 + x5 )(1 + x + x2 + x3 + x5 )
× (1 + x + x2 + x4 + x5 )(1 + x + x3 + x4 + x5 )(1 + x2 + x3 + x4 + x5 )
Для создания проверочных полиномов можно брать произвольную комбинацию функ-
ций ψ, например p = ψ1 ψ3 ... (кроме ψ0 = 1 + x).
Заметим, что длина кода и количество исправляемых ошибок напрямую связа-
ны с размерностью поля GF (2m ). Обозначим через [n, k, q] код, длиной n с k ин-
формационными разрядами, исправляющий q ошибок. Тогда поле GF (2m ) допускает
построение следующих кодов БЧХ
F GF (22) : [3, 1, 1]
3
F GF (2 ) : [7, 4, 1], [7, 1, 2]
F GF (24) : [15, 11, 1], [15, 7, 2], [15, 5, 3], [15, 1, 4]
Существует множество различных алгоритмов декодирования кода БЧХ. Мы рас-
смотрим некоторые из них.
или
q q
X Y
j
Σ(x) = σj x = (1 + 2αj x)
j=0 j=0
x7 − 1 = ψ0 ψ1 ψ2 = (1 + x)(1 + x + x3 )(1 + x2 + x3 )
x3 Q R x6 + x3 3 x2 + x
=C+ или = (x + x) +
p p x3 + x + 1 x3 + x + 1
m(x) = x6 + x5 + x4 + x3 = 1001000
m = 1001000
R= 110
F = 1001110
F = (1011110) → F = (1001110).
Задача 3.16.
На приемнике была получена кодовая последовательность БЧХ [7,4] над GF (23 ).
Восстановить исходное сообщение.
N F N F N F
1 1110001 11 0101001 21 1001001
2 0111010 12 1101010 22 0001010
3 1010011 13 0100011 23 1100011
4 1011100 14 0001100 24 1101100
5 0100001 15 1101110 25 0011111
6 0100111 16 1110110 26 0100111
7 0100100 17 1000110 27 0001011
8 1100111 18 0100110 28 0001101
9 1100100 19 1001111 29 0001110
10 1100010 20 0101111 30 1110010
p = ψ1 ψ2 = (1 + x + x3 )(1 + x2 + x3 ) = 1 + x + x2 + x3 + x4 + x5 + x6 .
Т.е. нам необходимо взять r = 6 проверочных символов для построения кода БЧХ
[7, 1] исправляющего 2 ошибки5 .
Допустим информационная последовательность имеет вид a = (1) представляется
в виде
Q(x) = 1.
Поскольку r = 6, то умножаем
m(x) = xr Q = x6 · 1 = x6 = 1000000.
x6 Q R
=C+
p p
или
x6 1 + x + x2 + x3 + x4 + x5
= 1 +
1 + x + x2 + x3 + x4 + x5 + x6 1 + x + x2 + x3 + x4 + x5 + x6
окуда получим R = 1 + x + x2 + x3 + x4 + x5 . Поскольку
m(x) = x6 = 1000000
m = 1000000
R = 111111
F = 1111111
F = (1111111) → F = (1011011)
7 5
∆2 = = 7·7−7·5= 3+6 =5
7 7
3 7
∆1 = = 3·7−5·7= 2+6 =4
5 7
По таблице умножения в GF (23 ) получим
∆−1 = 5−1 = 2.
Тогда
∆1
σ1 = = ∆1 · ∆−1 = 4 · 2 = 3
∆
∆2
σ2 = = ∆2 · ∆−1 = 5 · 2 = 1
∆
Теперь подставим полученные значения (σ1 , σ2 ) в уравнение
Задача 3.17.
На приемнике была получена кодовая последовательность БЧХ [7,1] над GF (23 ).
Восстановить исходное сообщение.
N F N F N F
1 0101111 11 1100111 21 0101111
2 0110111 12 1101011 22 0110111
3 0111011 13 1101101 23 0111011
4 0111101 14 1101110 24 0111101
5 0111110 15 1110011 25 0111110
6 1001111 16 1110101 26 1001111
7 1010111 17 1110110 27 1010111
8 1011011 18 1111001 28 1011011
9 1011101 19 1111010 29 1011101
10 1011110 20 1111100 30 1011110
x4 Q R
=C+
p p
или
x14 + x13 + x12 + x8 + x7 + x6 2 4 7 8 9 1 + x3
= 1 + x + x + x + x + x + x +
x4 + x + 1 x4 + x + 1
окуда получим R = x3 + 1 = (1001). Поскольку
m = 111000111000000
R= 1001
F = 111000111001001
F = (111000111001001) → F = (111010111001001)
F = (111010111001001) → F = (111000111001001)
150 Глава 3. Теория помехоустойчивого кодирования
Задача 3.18.
На приемнике была получена кодовая последовательность БЧХ [15, 11] над GF (24 ).
Восстановить исходное сообщение.
N F N F N F
1 111100001111110 11 110011001100011 21 101010101011001
2 111100001111000 12 110011001100001 22 101010101011111
3 111100001110100 13 110011001100111 23 101010101010011
4 111100001101100 14 110011001101011 24 101010101001011
5 111100001011100 15 110011001110011 25 101010101111011
6 111100000111100 16 110011001000011 26 101010100011011
7 111100011111100 17 110011000100011 27 101010111011011
8 111100101111100 18 110011011100011 28 101010001011011
9 111101001111100 19 110011101100011 29 101011101011011
10 111110001111100 20 110010001100011 30 101000101011011
p = ψ2 ψ4 = (1 + x + x4 )(1 + x + x2 + x3 + x4 ) = 1 + x4 + x6 + x7 + x8
m = 111000100000000
R= 01110111
F = 111000101110111
F = (111000101110111) → F = (110000111110111)
N F N F N F
1 111110111100101 11 110110111111000 21 101001100111110
2 111000111100101 12 111010111111000 22 100101100111110
3 111010011100101 13 111100111111000 23 100011100111110
4 111010101100101 14 111111111111000 24 100000100111110
5 111010110100101 15 111110011111000 25 100001000111110
6 111010111000101 16 111110101111000 26 100001110111110
7 101111111100101 17 111110110111000 27 100001101111110
8 101110011100101 18 111110111011000 28 100001100011110
9 101110101100101 19 111110111101000 29 100001100101110
10 101110110100101 20 111110111110000 30 100001100110110
3.7. Коды БЧХ 153
9 14 4 9 13 14
∆2 = 13 6 14 =9 ∆1 = 13 4 6 =7
4 3 6 4 14 3
По таблице умножения в GF (24 ) получим
∆−1 = 14−1 = 3.
Тогда
∆1
σ1 = = ∆1 · ∆−1 = 7 · 3 = 9
∆
∆1
σ2 = = ∆2 · ∆−1 = 9 · 3 = 8
∆
∆1
σ1 = = ∆1 · ∆−1 = 5 · 3 = 15
∆
Теперь подставим полученные значения (σ1 , σ2 , σ3 ) в уравнение
Σ(x) = 1 + σ1 x + σ2 x2 + σ3 x3 = 1 + 9x + 8x2 + 15x3
= (1 + 3x)(1 + 7x)(1 + 13x)
= (1 + 24 x)(1 + 210 x)(1 + 213 x).
3.7. Коды БЧХ 155
F = (101111011011000) → F = (111101011001000)
Задача 3.20.
На приемнике была получена кодовая последовательность БЧХ [15, 5] над GF (24 ).
Восстановить исходное сообщение.
N F N F N F
1 110011110101111 11 111011001000001 21 100111000010111
2 110011110101001 12 111011001001101 22 100111000010001
3 110011110100101 13 111011001010101 23 100111000011101
4 110011110111101 14 111011001100101 24 100111000000101
5 110011110001101 15 111011000000101 25 100111000110101
6 110011111101101 16 111011011000101 26 100111001010101
7 110011100101101 17 111011101000101 27 100111010010101
8 110011010101101 18 111010001000101 28 100111100010101
9 110010110101101 19 111001001000101 29 100110000010101
10 110001110101101 20 111111001000101 30 100101000010101
Для кодов исправляющих 1-2 ошибки можно предложить еще один эффективный
метод декодирования. Допустим вектор F содержит две ошибки e(x) = xα +xβ , тогда
S1 = 2 α + 2 β S3 = 23α + 23β .
S1 = η1 + η2 S3 = η13 + η23
поэтому
1 + S1 x + S12 + S3 S1−1 x2 = 0
1 + S1 x = 0
1 + σ1 x + σ2 x2 + ... + σk xk = 0
F Коррекция 1 ошибки σ1 = S1
F Коррекция 2 ошибок σ1 = S1
S3 + S13
σ2 =
S1
F Коррекция 3 ошибок σ1 = S1
S12 S3 + S5
σ2 = , σ3 = S13 + S3 + S1 σ2
S3 + S13
F Коррекция 4 ошибок σ1 = S1
F Коррекция 5 ошибок σ1 = S1
(S13 +S3 )[S19 +S9 +S14 (S5 +S13 S3 )+S32 (S13 +S3 )]+(S15 +S5 )(S17 +S7 )+S1 (S32 +S1 S5 )
σ2 = (S13 +S3 )[S7 +S17 +S1 S3 (S13 +S3 )]+(S5 +S12 S3 )(S15 +S5 )
σ3 = S13 + S3 + S1 σ2
σ5 = S5 + S12 S3 + S1 S4 + σ2 (S13 + S3 )
3.7. Коды БЧХ 157
Q = S · q0 + r1
тогда
S = r1 · q1 + r2
r1 = r2 · q2 + r3
r2 = r3 · q3 + r5
...
F 1 ошибка
σ1 = σ0 q0 = q0
Т.к.
Q = x3 и S(x) = 1 + S1 x + S2 x2 = 1 + S1 x + S12 x2
найдем q0
Q = S · q0 + r1
3 1 + S1 x 1
x = (1 + S1 x + S12 x2 ) +
S13 S13
1+S1 x
т.е. q0 = S13
тогда σ = 1 + S1 x
F 2 ошибки
σ2 = σ1 q1 + σ0 = q0 q1 + 1
нам необходимо найти q0 и q1 из последовательности выражений
Q = S · q0 + r1
S = r1 · q1 + r2
Т.к.
Q = x5 и S(x) = 1 + S1 x + S12 x2 + S3 x3 + S14 x2
158 Глава 3. Теория помехоустойчивого кодирования
получим
S3 + S14 x
5
x = (1 + S1 x + S12 x2
+ S3 x + 3
S14 x2 )
S1
S3 + (S1 S3 + S1 )x + (S1 + S1 S3 )x + (S15 + S12 S3 )x2
4 5 2
+
S1
S +S 4 x
т.е. q0 = 3 S1 1 .
Далее
F 3 ошибки
σ3 = σ2 q2 + σ1 = q0 q1 q2 + q0 + q2
F 4 ошибки
σ4 = σ3 q3 + σ2 = q0 q1 q2 q3 + q0 q3 + q2 q3 + q1 q0 + 1
3.8. Совершенные недвоичные коды 159
qm − 1
n= , n − m, 3 и [11, 6, 5]3.
q−1 q
Все совершенные двоичные коды могут быть построены методом Хэмминга [2]. Для
совершенных недвоичных кодов над Zp математических проблем не возникает. По-
строение же кодов над GF (pm ) требует разработки новых методов. Это связано
с тем, что кольцо Zpm не является полем. Так в [3] для кодирования в GF (2m )
предлагается использовать дискретное преобразование Фурье. Для построения ко-
да Рида-Соломона в [4] вводятся специфические законы сложения и умножения.
Однако полученные коды имеют, соответственно, параметры [n, k] = [2m , 2m−1 ] и
[n, k] = [2m − 1, 2m − 3] и не являются совершеннными. Несмотря на сомнитель-
ную практическую значимость, работы по созданию новых кодов над полями ма-
лых размерностей ведутся достаточно интенсивно [5], поскольку дают взможность
отработать новые алгоритмы и методы. Аналогично, одной из основных причин при-
стального внимания к совершеннным кодам является то, что они нередко становятся
базисными для построения других кодов. Удачно построенный алгоритм позволяет
оставаться вблизи границы Синглтона даже при значительном расширении и изме-
нении совершенного кода. В настоящей работе предлагается простой алгоритм по-
строения совершенного кода над GF (2m ).
x0 x1
= 1 = 001; = x = 010
p(x) p(x)
x2
3
x
= x2 = 011; = x + 1 = 001
p(x) p(x)
n 0 1 2 3
2n 1 2 3 1
ind n 3 0 1 2
F = (a1 a2 a3 e1 e2 ).
F = (a1 a2 a3 e1 e2 ).
E = e1 + e1 ,
3
где e1 = ak , а позициция ошибки j
P
k=1
e2 + e2
j= ,
E
3
где e2 = kek . Если j = 0 или E = 0, то ошибка в проверочных символах.
P
k=1
Пример 36. Закодировать сообщение a = (321).
Решение. Пользуясь таблицами сложения и умножения поля GF (22 ) найдем про-
верочные символы
X X
e1 = ak = 3 + 2 + 1 = 0, e2 = kak = 1 · 3 + 2 · 2 + 3 · 1 = 3 + 3 + 3 = 3.
E = e1 + e1 = 0 + 3 = 3,
а позициция ошибки j
e2 + e2 3+2 1
j== = = 2.
E E 3
Прибавляя E = 3 ко второму символу a2 + E = 1 + 3 = 2 получим информационную
комбинацию a = (321). N
N F N F N F N F
1 (2, 2, 1, 1, 3) 9 (3, 2, 2, 2, 0) 17 (2, 0, 2, 2, 0) 25 (3, 1, 2, 1, 3)
2 (1, 2, 2, 2, 0) 10 (2, 1, 0, 1, 1) 18 (3, 3, 3, 1, 3) 26 (1, 0, 3, 0, 2)
3 (0, 2, 2, 2, 0) 11 (3, 2, 3, 1, 3) 19 (2, 3, 1, 2, 2) 27 (0, 3, 0, 2, 2)
4 (2, 1, 1, 1, 1) 12 (3, 3, 1, 1, 3) 20 (1, 3, 1, 0, 2) 28 (1, 0, 2, 0, 2)
5 (3, 0, 3, 1, 3) 13 (3, 2, 0, 1, 3) 21 (1, 2, 1, 1, 3) 29 (3, 1, 0, 1, 3)
6 (1, 2, 1, 0, 2) 14 (3, 3, 1, 2, 2) 22 (3, 0, 1, 1, 3) 30 (2, 1, 2, 2, 0)
7 (1, 3, 1, 2, 2) 15 (2, 3, 2, 1, 0) 23 (3, 2, 3, 1, 3) 31 (0, 2, 1, 1, 3)
8 (2, 2, 3, 2, 0) 16 (2, 1, 3, 1, 1) 24 (3, 1, 1, 1, 3) 32 (3, 1, 1, 1, 3)
F = (a1 a2 a3 a4 a5 a6 a7 e1 e2 ).
162 Глава 3. Теория помехоустойчивого кодирования
F = (a1 a2 a3 a4 a5 a6 a7 e1 e2 ).
E = e1 + e1 ,
7
где e1 = ak , а позициция ошибки j
P
k=1
e2 + e2
j= ,
E
7
где e2 = kek . Если j = 0 или E = 0, то ошибка в проверочных символах.
P
k=1
Пример 38. Закодировать сообщение a = (6543456).
Решение. Пользуясь таблицами сложения и умножения поля GF (23 ) найдем про-
верочные символы
X
e1 = ak = 6 + 5 + 4 + 3 + 4 + 5 + 6 = 3,
X
e2 = kak = 1 · 6 + 2 · 5 + 3 · 4 + 4 · 3 + 5 · 4 + 6 · 5 + 7 · 6 = 6 + 1 + 7 + 7 + 2 + 3 + 4 = 2
Т.о. кодовая комбинация принимает вид F = (654345632). N
Допустим во время передачи информации в сообщении появилась ошибка во 3-м
символе
F = (651345632).
Пример 39. Обнаружить и исправить ошибку в сообщении F = (651345632).
Решение. Из принятой кодовой комбинации имеем (e1 = 3, e2 = 2). Пользуясь
таблицами сложения и умножения поля GF (23 ) найдем новые проверочные символы
X
e1 = ak = 6 + 5 + 1 + 3 + 4 + 5 + 6 = 6,
X
e2 = kak = 1 · 6 + 2 · 5 + 3 · 1 + 4 · 3 + 5 · 4 + 6 · 5 + 7 · 6 = 6 + 1 + 3 + 7 + 2 + 3 + 4 = 6
Тогда значение ошибки E вычисляется по формуле
E = e1 + e1 = 3 + 6 = 5,
а позициция ошибки j
e2 + e2 2+6 4
j= = = = 4 · 2 = 3.
E E 5
Прибавляя E = 5 к третьему символу a3 + E = 1 + 5 = 4 выделим информационную
комбинацию a = (6543456). N
3.8. Совершенные недвоичные коды 163
N F N F N F
1 (4, 4, 4, 3, 5, 2, 6, 1, 6) 11 (2, 3, 2, 1, 6, 4, 0, 7, 6) 21 (1, 2, 3, 2, 7, 5, 1, 7, 2)
2 (2, 3, 5, 1, 2, 3, 6, 3, 3) 12 (4, 6, 4, 3, 5, 2, 6, 1, 6) 22 (6, 3, 2, 2, 7, 0, 7, 2, 7)
3 (1, 2, 0, 2, 1, 5, 1, 7, 2) 13 (2, 3, 4, 0, 2, 3, 6, 3, 3) 23 (4, 2, 4, 3, 5, 2, 6, 1, 6)
4 (2, 3, 2, 0, 2, 3, 6, 0, 0) 14 (4, 3, 5, 0, 6, 7, 3, 2, 0) 24 (2, 0, 4, 1, 2, 3, 6, 3, 3)
5 (2, 3, 2, 5, 1, 4, 0, 7, 6) 15 (1, 2, 3, 2, 6, 5, 1, 7, 2) 25 (2, 3, 2, 1, 1, 4, 4, 7, 6)
6 (2, 3, 4, 1, 2, 3, 3, 3, 3) 16 (4, 3, 2, 1, 1, 1, 3, 0, 5) 26 (4, 3, 2, 0, 1, 6, 3, 0, 5)
7 (2, 3, 2, 5, 1, 3, 6, 1, 6) 17 (2, 3, 2, 4, 2, 3, 0, 0, 0) 27 (0, 3, 5, 2, 6, 7, 3, 2, 0)
8 (6, 3, 2, 1, 1, 6, 3, 0, 5) 18 (2, 3, 4, 1, 2, 6, 6, 3, 3) 28 (2, 0, 2, 3, 1, 3, 6, 1, 6)
9 (4, 3, 5, 2, 0, 7, 3, 2, 0) 19 (2, 0, 5, 5, 1, 3, 6, 1, 6) 29 (2, 0, 2, 4, 2, 3, 6, 0, 0)
10 (1, 7, 2, 2, 7, 0, 7, 2, 7) 20 (1, 4, 2, 2, 7, 0, 7, 2, 7) 30 (2, 3, 4, 5, 2, 3, 6, 3, 3)
164 Глава 3. Теория помехоустойчивого кодирования
b=0:
2t−1
Y
g(x) = (x ⊕ 2i ) = (x ⊕ 20 )(x ⊕ 21 ) = x2 + (1 + 2)x + (1 · 2) = x2 + 3x + 2,
i=0
b=1:
2t
Y
g(x) = (x ⊕ 2i) = (x ⊕ 21 )(x ⊕ 22 ) = x2 + (2 + 4)x + (2 · 4) = x2 + 6x + 3,
i=1
b=2:
2t+1
Y
g(x) = (x ⊕ 2i ) = (x ⊕ 22 )(x ⊕ 23 ) = x2 + (4 + 3)x + (4 · 3) = x2 + 7x + 7. N
i=2
b g(x) ci di
2
0 x + 3x + 2 (5, 2, 4, 7, 3) (4, 3, 5, 6, 2)
1 x2 + 6x + 3 (6, 7, 7, 1, 6) (2, 2, 3, 1, 3)
2 x2 + 7x + 7 (4, 4, 2, 4, 7) (1, 5, 1, 3, 7)
3 x2 + 5x + 1 (1, 5, 6, 6, 5) (5, 6, 6, 5, 1)
4 x2 + 1x + 4 (7, 3, 1, 5, 1) (7, 4, 2, 4, 4)
5 x2 + 2x + 6 (3, 1, 3, 2, 2) (6, 1, 7, 7, 6)
6 x2 + 4x + 5 (2, 6, 5, 3, 4) (3, 7, 4, 2, 5)
m(x) = xr u(x).
F = a0 a1 a2 a3 a4 e1 e2
или
F (x) = a0 x6 + a1 x5 + a2 x4 + a3 x3 + a4 x2 + e1 x + e2 .
166 Глава 3. Теория помехоустойчивого кодирования
F (x) = A6 x6 + A5 x5 + A4 x4 + A3 x3 + A2 x2 + A1 x + A0 .
Решая уравнение
S1 = S0 σ
по таблице индексов для GF (23 ) находим локатор ошибки
λ = ind σ
и значение ошибки
S0 = σ b E.
Ошибка величиной E находится на λ месте кодовой последовательности.
Очевидно, что размерность синдрома позволяет локализовать только 7 разрядов,
поэтому прямой алгебраический метод применяется для кода [7,5], с пятью инфор-
мационными символами.
или
e1 = 5 · 2 + 2 · 0 + 4 · 1 + 7 · 0 + 3 · 5 = 1 + 4 + 4 = 1,
e2 = 4 · 2 + 3 · 0 + 5 · 1 + 6 · 0 + 2 · 5 = 3 + 5 + 1 = 7.
F (x) = 2 · x6 + 0 · x5 + 1 · x4 + 5 · x3 + 5 · x2 + 1 · x1 + 7 · 1,
S0 = F (2b), и S1 = F (2b+1 ).
3.9. Коды Рида-Соломона 167
S0 = F (20 ) = F (1) = 2 · 16 + 0 · 15 + 1 · 14 + 5 · 13 + 5 · 12 + 1 · 1 + 7
= 2 + 1 + 5 + 5 + 1 + 7 = 5,
1
S1 = F (2 ) = F (2) = 2 · 26 + 0 · 25 + 1 · 24 + 5 · 23 + 5 · 22 + 1 · 2 + 7,
= 2 · 5 + 0 · 7 + 1 · 6 + 5 · 3 + 5 · 4 + 1 · 2 + 7,
= 1 + 6 + 4 + 2 + 2 + 7 = 4.
S1 = S0 σ, 4 = 5σ ⇒ σ = 4 · 5−1 .
σ = 4 · 5−1 = 4 · 2 = 3.
λ = ind σ, λ = ind 3 = 3.
S0 = σ b E, 5 = 1 · E.
F = (2015517) → F = (2010517)
e1 = (a · c) = (54321)(44247),
e2 = (a · d) = (54321)(15137)
или
e1 = 5 · 4 + 4 · 4 + 3 · 2 + 2 · 4 + 1 · 7 = 2 + 6 + 6 + 3 + 7 = 6,
e2 = 5 · 1 + 4 · 5 + 3 · 1 + 2 · 3 + 1 · 7 = 5 + 2 + 3 + 6 + 7 = 5.
6
Данный результат F = (2010517) можно проверить следующими способами.
a) Если для a = (20105) мы получим e1 = 1, e2 = 7, то задача решена правильно.
b) Если для F = (2010517) мы получим S0 = 0, S1 = 0, то задача решена правильно.
168 Глава 3. Теория помехоустойчивого кодирования
F (x) = 5 · x6 + 7 · x5 + 3 · x4 + 2 · x3 + 1 · x2 + 6 · x1 + 5 · 1,
S0 = F (2b), и S1 = F (2b+1 ).
S0 = F (22) = F (4) = 5 · 46 + 7 · 45 + 3 · 44 + 2 · 43 + 1 · 42 + 6 · 4 + 5
= 5·7+7·3+3·2+2·5+1·6+6·4+5
= 6 + 2 + 6 + 1 + 6 + 5 + 5 = 5,
S1 = F (23) = F (3) = 5 · 36 + 7 · 35 + 3 · 34 + 2 · 33 + 1 · 32 + 6 · 3 + 5
= 5 · 36 + 7 · 35 + 3 · 34 + 2 · 33 + 1 · 32 + 6 · 3 + 5
= 5·6+7·2+3·7+2·4+1·5+6·3+5
= 3 + 5 + 2 + 3 + 5 + 1 + 5 = 6.
S1 = S0 σ, 6 = 5σ ⇒ σ = 7.
λ = ind σ, λ = ind 7 = 5.
S0 = σ b E, 5 = 72 · E = 3 · E ⇒ E = 3.
F = (5732165) → F = (5432165)
N g(x) F N g(x) Fi
2 2
1 x + 3x + 2 (2, 0, 1, 7, 5, 7, 4) 16 x + 6x + 3 (7, 0, 1, 7, 5, 6, 3)
2 x2 + 6x + 3 (5, 6, 1, 5, 5, 7, 2) 17 x2 + 7x + 7 (5, 6, 3, 5, 7, 0, 5)
3 x2 + 7x + 7 (6, 3, 3, 4, 2, 7, 4) 18 x2 + 5x + 1 (6, 6, 1, 7, 5, 5, 2)
4 x2 + 5x + 1 (4, 5, 1, 3, 1, 5, 3) 19 x2 + 1x + 4 (7, 0, 4, 5, 2, 6, 1)
5 x2 + 1x + 4 (5, 5, 4, 4, 2, 2, 2) 20 x2 + 2x + 6 (4, 5, 1, 7, 3, 5, 7)
6 x2 + 2x + 6 (6, 4, 1, 0, 7, 4, 7) 21 x2 + 4x + 5 (1, 0, 0, 5, 2, 2, 1)
7 x2 + 4x + 5 (7, 0, 0, 4, 2, 6, 2) 22 x2 + 3x + 2 (4, 0, 3, 7, 5, 7, 0)
8 x2 + 3x + 2 (2, 5, 1, 7, 4, 5, 2) 23 x2 + 6x + 3 (6, 5, 1, 4, 5, 5, 3)
9 x2 + 6x + 3 (0, 3, 1, 5, 4, 4, 1) 24 x2 + 7x + 7 (6, 6, 2, 5, 6, 2, 0)
10 x2 + 7x + 7 (4, 5, 6, 3, 4, 5, 6) 25 x2 + 5x + 1 (7, 5, 3, 4, 5, 6, 5)
11 x2 + 5x + 1 (5, 3, 1, 5, 5, 6, 4) 26 x2 + 1x + 4 (0, 3, 1, 5, 6, 1, 2)
12 x2 + 1x + 4 (6, 3, 5, 3, 5, 1, 7) 27 x2 + 2x + 6 (1, 0, 3, 4, 3, 4, 6)
13 x2 + 2x + 6 (7, 4, 1, 5, 2, 7, 4) 28 x2 + 4x + 5 (2, 4, 4, 5, 5, 2, 5)
14 x2 + 4x + 5 (1, 5, 1, 3, 5, 4, 2) 29 x2 + 3x + 2 (2, 3, 1, 1, 3, 4, 4)
15 x2 + 3x + 2 (3, 4, 2, 1, 5, 2, 1) 30 x2 + 6x + 3 (5, 4, 3, 2, 1, 5, 0)
170 Глава 3. Теория помехоустойчивого кодирования
b g(x) ci di hi fi
0 x4 + 4x3 + 7x2 + 7x + 5 (2, 1, 4) (3, 6, 7) (5, 4, 7) (5, 2, 5)
1 x4 + 3x3 + x2 + 2x + 3 (6, 4, 3) (1, 1, 1) (6, 5, 2) (7, 5, 3)
2 x4 + 6x3 + 4x2 + 6x + 1 (1, 6, 6) (6, 3, 4) (4, 3, 6) (6, 6, 1)
3 x4 + 7x3 + 6x2 + x + 6 (3, 5, 7) (2, 5, 6) (1, 1, 1) (3, 4, 6)
4 x4 + 5x3 + 5x2 + 3x + 2 (5, 2, 5) (7, 4, 5) (7, 6, 3) (4, 1, 2)
5 x4 + x3 + 2x2 + 5x + 7 (4, 3, 1) (4, 7, 2) (3, 2, 5) (2, 7, 7)
6 x4 + 2x3 + 3x2 + 4x + 4 (7, 7, 2) (5, 2, 3) (2, 7, 4) (1, 3, 4)
3.9. Коды Рида-Соломона 171
F = a0 a1 a2 e1 e2 e3 e4
или
F (x) = a0 x6 + a1 x5 + a2 x4 + e1 x3 + e2 x2 + e3 x + e4 .
Допустим, принятая кодовая комбинация
F (x) = A6 x6 + A5 x5 + A4 x4 + A3 x3 + A2 x2 + A1 x + A0 .
Sk = F (2b+k ).
S0 = F (20 ) = F (1) = a1 16 + a2 15 + a3 14 + e3 13 + e4 12 + e5 11 + e4 ,
S1 = F (21 ) = F (2) = a1 26 + a2 25 + a3 24 + e3 23 + e4 22 + e5 21 + e4 ,
S2 = F (22 ) = F (4) = a1 46 + a2 45 + a3 44 + e3 43 + e4 42 + e5 41 + e4 ,
S3 = F (23 ) = F (3) = a1 36 + a2 35 + a3 34 + e3 33 + e4 32 + e5 31 + e4 .
Решая уравнение
S2 S0 S1 σ2
=
S3 S1 S2 σ1
находим многочлен локаторов ошибок
ν
Y
2
σ(x) = 1 + σ1 x + σ2 x = (1 + αk x)
k=1
или
F (x) = 7 · x6 + 6 · x5 + 6 · x4 + 7 · x3 + 3 · x2 + 6 · x1 + 3 · 1,
S0 = F (2b) = 7 · 16 + 6 · 15 + 6 · 14 + 7 · 13 + 3 · 12 + 6 · 1 + 3 = 6
S1 = F (2b+1 ) = 7 · 26 + 6 · 25 + 6 · 24 + 7 · 23 + 3 · 22 + 6 · 2 + 3 = 1,
S2 = F (2b+2 ) = 7 · 46 + 6 · 45 + 6 · 44 + 7 · 43 + 3 · 42 + 6 · 4 + 3 = 4,
S3 = F (2b+3 ) = 7 · 36 + 6 · 35 + 6 · 34 + 7 · 33 + 3 · 32 + 6 · 3 + 3 = 0.
4 1
∆2 = = 4·4−0·1= 6+0= 6
0 4
6 4
∆1 = = 6·0−1·4= 0+4= 4
1 0
3.9. Коды Рида-Соломона 173
σ(x) = 1 + σ1 x + σ2 x2 = 1 + x + 4x2 .
1 1
∆= = 1·7−6·1= 7+6= 1
6 7
6 1
∆1 = = 6·7−1·1= 4+1 =5
1 7
1 6
∆2 = = 1·1−6·6= 1+2 =3
6 1
Тогда
∆1 5 ∆2 3
e1 = = = 5, e2 = = = 3.
∆ 1 ∆ 1
174 Глава 3. Теория помехоустойчивого кодирования
Из таблицы коэффициентов для кода [7, 3]8 для b=3, g(x) = x4 + 7x3 + 6x2 + x + 6
имеем:
c = (357), d = (256), h = (111), f = (346)
или
e1 = (a · c) = 2 · 3 + 6 · 5 + 4 · 7 = 6 + 3 + 1 = 4,
e2 = (a · d) = 2 · 2 + 6 · 5 + 4 · 6 = 4 + 3 + 5 = 2,
e3 = (a · h) = 2 · 1 + 6 · 1 + 4 · 1 = 2 + 6 + 4 = 0,
e4 = (a · f ) = 2 · 3 + 6 · 4 + 4 · 6 = 6 + 5 + 5 = 6.
Код Рида-Соломона для данной информационной последовательности имеет вид
F = (2644206).
Допустим в передаваемой кодовой последовательности возникли ошибки в 2 и 6
разряде F = (2644206) ⇒ F = (7644606). Учитывая, что
F (x) = 7 · x6 + 6 · x5 + 4 · x4 + 4 · x3 + 6 · x2 + 0 · x1 + 6 · 1,
определяем синдром ошибки при b=3 с помощью выражений
S0 = F (2b ) = F (23 ) = F (3)
= 7 · 36 + 6 · 35 + 4 · 34 + 4 · 33 + 6 · 32 + 0 · 3 + 6
= 7·6+6·2+4·7+4·4+6·5+0·3+6
= 4+7+1+6+3+0+6 =1
7
Данный результат F = (7537363) можно проверить следующими способами.
a) Если для a = (753) мы получим e = (7363), то задача решена правильно.
b) Если для F = (7537363) мы получим S0 = S1 = S2 = S3 = 0, то задача решена правильно.
3.9. Коды Рида-Соломона 175
1 7
∆= = 1·5−7·7= 5+3= 6
7 5
5 7
∆2 = = 5·5−0·7= 7+0 =7
0 5
1 5
∆1 = = 1·0−7·5= 0+6 =6
7 0
Из таблицы умножения для GF (23 ) видим, что 6 · 3 = 1, т.е. обратным элементом
для 6 является 3. Тогда
∆2 7 ∆1 6
σ2 = = = 7 · 3 = 2, σ1 = = = 6 · 3 = 1.
∆ 6 ∆ 6
Построим многочлен локаторов ошибки
σ(x) = 1 + σ1 x + σ2 x2 = 1 + x + 2x2 .
176 Глава 3. Теория помехоустойчивого кодирования
5 6
∆= = 5·3−2·6= 4+7= 3
2 3
1 6
∆1 = = 1·3−7·6= 3+4= 7
7 3
5 1
∆2 = = 5·7−2·1= 6+2= 4
2 7
Тогда
∆1 7 ∆2 4
e1 = = = 7 · 6 = 4, e2 = = = 4 · 6 = 5.
∆ 3 ∆ 3
Т.о. мы имеем ошибку в разряде x2 со значением E2 = 4 и в разряде x6 со значением
E6 = 5. Исправляя ошибки, получим
F = (7644606) ⇒ F = (2644206)
F (x) = 6 · x6 + 2 · x5 + 5 · x4 + 4 · x3 + 4 · x2 + 2 · x1 + 0 · 1,
7 4
∆= = 7·5−4·4= 6+6= 0
4 5
5 4
∆2 = = 5·5−3·4= 7+7 =0
3 5
178 Глава 3. Теория помехоустойчивого кодирования
7 5
∆1 = = 7·3−4·5= 2+2= 0
4 3
S0 = σ b E или 7 = 64 E = 4E ⇒ E = 4−1 7 = 7 · 7 = 3.
F = (6254420) ⇒ F = (6264420)
N g(x) Fi N g(x) Fi
1 x4 + 4x3 + 7x2 + 7x + 5 (4562373) 16 x4 + 3x3 + 1x2 + 2x + 3 (1615153)
2 x4 + 3x3 + 1x2 + 2x + 3 (2732576) 17 x4 + 6x3 + 4x2 + 6x + 1 (7563113)
3 x4 + 6x3 + 4x2 + 6x + 1 (1247370) 18 x4 + 7x3 + 6x2 + 1x + 6 (4431737)
4 x4 + 7x3 + 6x2 + 1x + 6 (5116230) 19 x4 + 5x3 + 5x2 + 3x + 2 (4661674)
5 x4 + 5x3 + 5x2 + 3x + 2 (2325111) 20 x4 + 1x3 + 2x2 + 5x + 7 (5564312)
6 x4 + 1x3 + 2x2 + 5x + 7 (3333005) 21 x4 + 2x3 + 3x2 + 4x + 4 (5471253)
7 x4 + 2x3 + 3x2 + 4x + 4 (4117765) 22 x4 + 4x3 + 7x2 + 7x + 5 (2715001)
8 x4 + 4x3 + 7x2 + 7x + 5 (2453626) 23 x4 + 3x3 + 1x2 + 2x + 3 (6262477)
9 x4 + 3x3 + 1x2 + 2x + 3 (0650027) 24 x4 + 6x3 + 4x2 + 6x + 1 (5525355)
10 x4 + 6x3 + 4x2 + 6x + 1 (0114252) 25 x4 + 7x3 + 6x2 + 1x + 6 (3270440)
11 x4 + 7x3 + 6x2 + 1x + 6 (2421121) 26 x4 + 5x3 + 5x2 + 3x + 2 (2264425)
12 x4 + 5x3 + 5x2 + 3x + 2 (3634162) 27 x4 + 1x3 + 2x2 + 5x + 7 (5253561)
13 x4 + 1x3 + 2x2 + 5x + 7 (3615206) 28 x4 + 2x3 + 3x2 + 4x + 4 (2727517)
14 x4 + 2x3 + 3x2 + 4x + 4 (2264027) 29 x4 + 4x3 + 7x2 + 7x + 5 (1426013)
15 x4 + 4x3 + 7x2 + 7x + 5 (3262616) 30 x4 + 3x3 + 1x2 + 2x + 3 (2535555)
9
Данный результат F = (6264420) можно проверить следующими способами.
a) Если для a = (626) мы получим e = (4420), то задача решена правильно.
b) Если для F = (6264420) мы получим S0 = S1 = S2 = S3 = 0, то задача решена правильно.
3.10. Алгоритм Берлекемпа-Месси 179
c+ = c + dBx = 1 + 1 · 1 · x = 1 + x
2L < i : 0 < 1 да ⇒ L = i − L, L = 1 − 0 = 1
c 1
B = = = 1, c = c+ = 1 + x
d 1
c+ = c + dBx = 1 + x + 6 · 1 · x = 1 + 7x
2L < i : 2 < 2 нет
B = xB = x, c = c+ = 1 + 7x
180 Глава 3. Теория помехоустойчивого кодирования
c+ = c + dBx = 1 + 7x + 6 · x · x = 1 + 7x + 6x2
2L < i : 2 · 1 < 3 да ⇒ L = i − L, L = 3 − 1 = 2
c 1 + 7x
B= = = 3(1 + 7x) = 3 + 2x, c = c+ = 1 + 7x + 6x2
d 6
F i = 4, d4 = (c1 , c2 , c3 , c4 ) · (s4 , s3 , s2 , s1 ) = (1, 7, 6, 0)(0, 5, 7, 1) = 1 · 0 + 7 · 5 + 6 ·
7+0·1=0+6+4+0=2
c+ = c + dBx = 1 + 7 · 1 · x = 1 + 7x
2L < i : 0 < 1 да ⇒ L = i − L, L = 1 − 0 = 1
c 1
B = = = 4, c = c+ = 1 + 7x
d 7
F i = 2, d2 = (c1 , c2 ) · (s2 , s1 ) = (1, 7)(4, 7) = 4 + 3 = 7
c+ = c + dBx = 1 + 7x + 7 · 4 · x = 1 + 7x + x = 1 + 6x
2L < i : 2 < 2 нет
B = Bx = 4x, c = c+ = 1 + 6x
B = Bx = 4x2 , c = 1 + 6x
B = Bx = 4x2 , c = 1 + 6x
N b F N b F N b F N b F
1 3 (2421121) 9 4 (2264425) 17 3 (5116230) 25 4 (4661674)
2 4 (3634162) 10 5 (5253561) 18 4 (2325111) 26 5 (5564312)
3 5 (3615206) 11 6 (2727517) 19 5 (3333005) 27 6 (5471253)
4 6 (2264027) 12 0 (1426013) 20 6 (4117765) 28 0 (2715001)
5 0 (3262616) 13 1 (2535555) 21 0 (2453626) 29 1 (6262477)
6 0 (4562373) 14 1 (1615153) 22 1 (0650027) 30 2 (5525355)
7 1 (2732576) 15 2 (7563113) 23 2 (0114252) 31 3 (3270440)
8 2 (1247370) 16 3 (4431737) 24 3 (2421121) 32 4 (2264425)
Q = S · q0 + r1
тогда
S = r1 · q1 + r2
r1 = r2 · q2 + r3
r2 = r3 · q3 + r5
...
F 1 ошибка
σ1 = σ0 q0 = q0
F 2 ошибки
σ2 = σ1 q1 + σ0 = q0 q1 + 1
F 3 ошибки
σ3 = σ2 q2 + σ1 = q0 q1 q2 + q0 + q2
F 4 ошибки
σ4 = σ3 q3 + σ2 = q0 q1 q2 q3 + q0 q3 + q2 q3 + q1 q0 + 1
182 Глава 3. Теория помехоустойчивого кодирования
Σ(x) = 1 + x + 2x2 . N
Σ(x) = 1 + 6x = 1 + 24 x. N
Σ(x) = 1 + σ1 x + σ2 x2 .
т.е.
x1 + x2 = σ1 x1 + x2 = 2
или
x1 · x2 = σ2 x1 · x2 = 5
По таблицам сложения и умножения для GF (23 ) находим x1 = 4, x2 = 6, тогда
1 1
∆= = 1·6−4·1= 6+4= 2
4 6
5 1
∆1 = = 5·6−7·1= 3+7 =4
7 6
1 5
∆2 = = 1·7−4·5= 7+2 =5
4 7
Тогда
∆1 4 ∆2 5
e1 = = = 4 · 5 = 2, e2 = = = 5 · 5 = 7.
∆ 2 ∆ 2
Т.о. мы имеем ошибку в разряде x со значением E2 = 2 и в разряде x4 со значением
2
F = (0070200) ⇒ (00000000) N
184 Глава 3. Теория помехоустойчивого кодирования
N b F N b F N b F N b F
1 4 (2264425) 9 3 (5116230) 17 4 (4661674) 25 3 (2421121)
2 5 (5253561) 10 4 (2325111) 18 5 (5564312) 26 4 (3634162)
3 6 (2727517) 11 5 (3333005) 19 6 (5471253) 27 5 (3615206)
4 0 (1426013) 12 6 (4117765) 20 0 (2715001) 28 6 (2264027)
5 1 (2535555) 13 0 (2453626) 21 1 (6262477) 29 0 (3262616)
6 1 (1615153) 14 1 (0650027) 22 2 (5525355) 30 0 (4562373)
7 2 (7563113) 15 2 (0114252) 23 3 (3270440) 31 1 (2732576)
8 3 (4431737) 16 3 (2421121) 24 4 (2264425) 32 2 (1247370)
Глава 4
Квантовая информация
185
186 Глава 4. Квантовая информация
θ θ
|ψi = cos |0i + eiφ sin |1i ,
2 2
и изображается точкой на сфере Блоха радиуса R = 1 и поверхностными коорди-
натами (θ, φ). В дальнейшем мы будем, как правило, работать с экваториальными
кубитами, (для которых φ = 0), и удваивать значение угла θ2 → θ для упрощения
записи:
|ψi = cos θ |0i + sin θ |1i .
z
1
θ ψ0
ψ0
ϕ
y 0 0
ϕ
x
a) b)
Таким образом
1 1
|ψ0 i = √ |0i + √ |1i . N
2 2
4.1. Основы квантовых вычислений 187
Π = |χi hχ| ,
χ
ψ0
ψ0
ψ1
ψ1
188 Глава 4. Квантовая информация
P = hψ|ψi = |ψ|2
или
√ √ !
1 3 3 3 1 1
|ψ 0 i = |0i h0| + |0i h1| + |1i h0| + |1i h1| √ |0i + √ |1i
4 4 4 4 2 2
√ √ !
1 1 3 1 3 1 3 1
= √ |0i h0|0i + √ |0i h1|0i + √ |1i h0|0i + √ |1i h1|0i
4 2 4 2 4 2 4 2
√ √ !
1 1 3 1 3 1 3 1
+ √ |0i h0|1i + √ |0i h1|1i + √ |1i h0|1i + √ |1i h1|1i
4 2 4 2 4 2 4 2
4.1. Основы квантовых вычислений 189
Учитывая, что
h0|0i = h1|1i = 1, h1|0i = h0|1i = 0,
получим
√ √ !
1 1 3 1 3 1 3 1
|ψ 0 i = √ |0i + √ |1i + √ |0i + √ |1i
4 2 4 2 4 2 4 2
√ √ !
1 1+ 3 3+ 3
= √ |0i + √ |1i
4 2 2
P = |hψ0 |χi|2
тогда
√ 2
2 1+ 3
P = |hψ0 |χi| = √ ≈ 0.933. N
2 2
√
Задача 4.2. Найти вероятность того, что квант |ψ0 i = 2
3
|0i + 21 |1i пройдет через
поляризатор, ориентированный под углом ϕ.
Однако столь быстрый метод работает только тогда, когда на кубит действует
только один оператор. Если же мы имеем последовательность операторов, то нам
необходимо вычислить состояние кубита после каждого преобразования.
Пример 4.3. На пути пучка квантов |ψ0 i = |0i ставится поляризационная пла-
стина №1, ориентированная под углом 0◦ . После нее ставится еще один поляризатор
№2 под углом 90◦ . Какова вероятность того, что исходный пучок пройдет через эти
два поляризатора.
Решение. Поставим в соответствие поляризатору №1 проекционный оператор
Π1 = |0i h0| ,
Π2 = |1i h1| .
а после второго
|ψ2 i = Π2 |ψ1 i = |1i h1|0i = |0i · 0.
Поэтому, вероятность прохождения кубитом двух поляризаторов равна
P = hψ2 |ψ2 i = 0. N
ψ0 0o 45
o
90
o
Π3 = |χi hχ| ,
где
1 1
|χi = √ |0i + √ |1i .
2 2
4.1. Основы квантовых вычислений 191
Тогда после прохождения первого поляризатора Π1 = |0i h0| кубит принимает состо-
яние
|ψ1 i = Π1 |ψ0 i = |0i h0|0i = |0i · 1 = |0i ,
после этого он проходит через поляризатор Π3 :
1 1 1 1
|ψ3 i = Π3 |ψ1 i = |χi hχ|0i = √ |0i + √ |1i √ h0|0i + √ h1|0i
2 2 2 2
1 1 1 1 1 1
= √ |0i + √ |1i √ · 1 + √ · 0 = |0i + |1i ,
2 2 2 2 2 2
а затем, через поляризатор Π2 = |1i h1|
1 1 1
|ψ2 i = Π2 |ψ3 i = |1i h1|ψ3 i = |1i h1| |0i + |1i = |1i .
2 2 2
Поэтому, вероятность прохождения кубитом трех поляризаторов равна
1 1
P = hψ2 |ψ2 i = h1|1i = . N
4 4
Последние два примера высвечивают один из основных фундаментальных прин-
ципов квантовой механики: операторы не просто проецируют кванты на собственное
состояние, а изменяют состояние кубита. Т.е. после взаимодействия с оператором ча-
стица становится другой и приобретает свойства уже этого оператора частично теряя
при этом некоторые свои свойства. Как видно из примеров квант горизонтальной по-
ляризации |0i не может пройти через ортогональный вертикально-ориентированный
поляризатор Π = |1i h1|. Однако, дополнительный оператор Π3 искажает исходное
состояние кубита, после чего он приобретает новые свойства, позволяющие пройти с
ненулевой вероятностью через ортогональный поляризатор.
Пример 4.5. На пути пучка квантов |ψ0 i = |0i ставится поляризационная пла-
стина №1, ориентированная под углом 0◦ . После нее ставится еще один поляризатор
№2 под углом 30◦ , далее поляризатор №3 под углом 45◦ , №4 - под углом 60◦ и №5
- под углом 90◦ . Какова вероятность того, что исходный пучок пройдет через эти 5
поляризаторов?
Решение. Поставим в соответствие поляризатору №1 проекционный оператор
Π1 = |0i h0| ,
поляризатору №2 - проекционный оператор
√ ! √ !
1 3 1 3
Π2 = |0i + |1i h0| + h1| ,
2 2 2 2
Π5 = |1i h1| .
Пример 4.6. На пути произвольного пучка квантов |ψ0 i = α |0i + β |1i ставится
поляризационная пластина №1, ориентированная под углом 0◦ . После нее ставится
еще один поляризатор №2 под углом 90◦ . Какова вероятность того, что исходный
пучок пройдет через эти два поляризатора.
Решение. Поставим в соответствие поляризатору №1 проекционный оператор
Π1 = |0i h0| ,
Π2 = |1i h1| .
Тогда
Π = |χi hχ| = (cos θ |0i + sin θ |1i) (h0| cos θ + h1| sin θ) .
Задача 4.3. На какой угол необходимо повернуть кубит |ψi чтобы получить
кубит |ψ 0 i ?
√ √ √ √ √
2+ 2 2− 2
1. |ψi = √ 2
|0i + 2 |1i |ψ 0 i = 1
2
|0i + √2
3
|1i
2. |ψi = 3
|0i + 1 |1i |ψ 0 i = 1 3
|0i + 2 |1i
√2 √ √ 2 √
2
√
2 5− 5
3. |ψi = √ 4√ |0i 5+1
√ 4√ |1i
+ |ψ 0 i = 23 √ |0i + 21 |1i
√ √
2+ 2 2− 2 2 5− 5
4. |ψi = 2
|0i + 2 |1i |ψ 0 i = 4
|0i
Π = |χi hχ| ,
на |ψi:
|ψ 0 i = Π |ψi = |χi hχ|ψi .
Выпишем явный вид квантового состояния прибора-измерителя:
|χi = σ1 |ψi = (|0i h1| + |1i h0|) (α |0i + β |1i) = α |1i + β |0i
тогда
Π = |χi hχ| = β 2 |0i h0| + αβ |0i h1| + αβ |1i h0| + α2 |1i h1|
и
|ψ 0 i = Π |ψi = |χi hχ | ψi
β 2 |0i h0| + αβ |0i h1| + αβ |1i h0| + α2 |1i h1| (α |0i + β |1i)
=
= β 2 α |0i + αβ 2 |0i + α2 β |1i + α2 β |1i = 2αβ 2 |0i + 2α2 β |1i = 2αβ |ψi
P = hψ 0 |ψ 0 i = 22 α2 β 2 hψ|ψi = 4α2 β 2 .
то из выражения
hψ|χi = (α h0| + β h1|) (β |0i + α |1i) = 2αβ
получим
P = |hψ|χi|2 = 4α2β 2 . N
Задача 4.4. Кубит имеет произвольное состояние |ψi = α |0i + β |1i. Найти
вероятность обнаружения его в состоянии
т.е. вероятность прохождения кванта |ψi через поляризатор Π = |χi hχ| равна 1. Та-
кой поляризатор мы назовем собственным для данного пучка. Любой произвольно
приготовленный пучок проходит через собственный поляризатор полностью, и об-
ратно, для любого поляризатора можно приготовить такой пучок который пройдет
через него без искажения (без потерь). Это дает основание рассматривать квантовые
пучки в терминах своих же собственных поляризаторов.
Матрицей плотности квантового пучка |ψi называется его собственный проек-
тор
ρ = |ψi hψ| .
Для кубита |ψ0 i = α |0i + β |1i часто используется расширенная запись его матрицы
плотности:
ρ0 = |ψ0 i hψ0 | = α2 |0i h0| + αβ |0i h1| + βα |1i h0| + β 2 |1i h1| .
или
α2 αβ
ρ0 = .
βα β 2
4.2. Матрица плотности 197
|ψ1 i = σ1 |ψ0 i = (|0i h1| + |1i h0|) (α |0i + β |1i) = α |1i + β |0i
тогда
ρ1 = |ψ1 i hψ1 | = α2 |1i h1| + αβ |0i h1| + αβ |1i h0| + β 2 |0i h0| . N
Задача 4.5. Найдите матрицу плотности квантового состояния |ψi = R (ϕ) |0i.
π π π π
1. ϕ = , 2. ϕ = , 3. ϕ = , 4. ϕ = .
8 5 6 4
Если для одного фотона всегда можно найти собственный проектор (поляриза-
тор, через который он проходит без искажения), то два фотона могут находится в
состояниях и с различной поляризацией. Тогда мы не сможем подобрать такую ори-
ентацию поляризатора, чтобы два фотона проходили через него без затухания. Если
для одного фотона данный поляризатор будет собственным, то для другого - нет, и
вероятность прохождения через него для второго фотона будет обязательно меньше
единицы.
Пучок фотонов, для которого существует собственный проектор называется чи-
стым.
Пучок фотонов, для которого собственного проектора не существует называется
смешанным.
198 Глава 4. Квантовая информация
где p1 + p2 = 1.
По матрице плотности чистого пучка ρ = |ψi hψ| можно однозначно восстановить
единственное квантовое состояние |ψi.
A2 + B 2 + C 2 + D 2 = 1.
сформирован состояниями
тогда
ρ = (p1 α12 + p2 α22 ) |0i h0| + (p1 α1 β1 + p2 α2 β2 )(|0i h1| + |1i h0|) + (p1 β12 + p2 β22 ) |1i h1| ,
или
A = p1 α12 + p2 α22
B = p1 α1 β1 + p2 α2 β2
C = p1 α1 β1 + p2 α2 β2
D = p1 β12 + p2 β22
и
A2 + B 2 + C 2 + D 2 = p21 + 2p1 p2 (α1 α2 + β1 β2 ) + p22 = 1.
Последнее равенство удовлетворяется только при
α1 α2 + β1 β2 = 1, ⇒ α1 = α2 ,
или
(p1 = 0, p2 = 1), или (p1 = 1, p2 = 0).
Все эти три решения соответствуют чистому пучку, а мы имеем критерий распозно-
вания чистого пучка. Аналогичным образом можно доказать утверждение для 3, 4
или n-кубитной смеси.
1X 1
ρ= pi σi = (p0 σ0 + p1 σ1 + p2 σ2 + p3 σ3 ) .
2 2
Сравнивая разложения
1
ρ = (p0 (|0i h0| + |1i h1|) + p1 (|0i h1| + |1i h0|)
2
+ ip2 (|1i h0| − |0i h1|) + p3 (|0i h0| − |1i h1|))
1
= ((p0 + p3 ) |0i h0| + (p1 − ip2 ) |0i h1|
2
+ (p1 + ip2 ) |1i h0| + (p0 − p3 ) |1i h1|)
и
ρ = A |0i h0| + B |0i h1| + C |1i h0| + D |1i h1|
200 Глава 4. Квантовая информация
получим систему
p0 = A + D
p1 = C + B
ip2 = C − B
p3 = A − D
получим √ √
1 3 3 9
A= , B= , C= , D=
4 4 4 4
откуда
1 3 3 9
A2 + B 2 + C 2 + D 2 =
+ + + = 1.
16 16 16 16
Поэтому наша матрица плотности образована чистым пучком. Тогда из определения
Π1 = |1i h1|
он пройдет с вероятностью β 2 .
Теперь возьмем два пучка
где
1 1
|ψ1 i = √ (|0i + |1i), |ψ2 i = √ (|0i − |1i), x ≤ 1.
2 2
202 Глава 4. Квантовая информация
то кубит
|ψ0 i = α |0i + β |1i
можно записать так
α
|ψi = ,
β
тогда в матричном представлении матрица плотности кубита
α
ρ = |ψi hψ| = · (α β)
β
имеет вид
α2 αβ
ρ= .
βα β 2
Отсюда и происходит ее название. Несмотря на то, что это представление является
неудобным для практических расчетов, оно очень эффективно для выяснения всех
свойств матрицы плотности.
Основные свойства матрицы плотности:
1) для чистого состояния
ρ2 = ρ;
2) след матрицы a = aik (spur-нем. или trace-англ) - есть сумма его диагональных
компонент:
a11 a12
Sp a = Sp = a11 + a22 ;
a21 a22
4.2. Матрица плотности 203
Sp ρ = 1.
или
A B
ρ= .
C D
Очевидно, что элементы (A, B, C, D) матрицы плотности ρ можно получить следую-
щим образом:
с помощью угла x мы получим полную группу событий: прохождение кубита |ψi че-
рез поляризатор |χi hχ|. Обозначим такой проекционный оператор через x = |χi hχ|.
204 Глава 4. Квантовая информация
записывается в виде
например:
|Ψi = a |00i + b |01i + c |10i + d |11i ,
где a2 + b2 + c2 + d2 = 1 - условие нормировки, (т.к. hΨ|Ψi = 1). Для такого дву-
мерного квантового состояния можно поставить в соответствие двумерную матрицу
плотности:
ρ = |Ψi hΨ| = a2 |00i h00| + ab |00i h01| + ac |00i h10| + ad |00i h11|
+ ba |01i h00| + b2 |01i h01| + bc |01i h10| + bd |01i h11|
+ ca |10i h00| + cb |10i h01| + c2 |10i h10| + cd |10i h11|
+ da |11i h00| + db |11i h01| + dc |11i h10| + d2 |11i h11|
или
a2 ab ac ad
|00i
ba b2 bc bd |01i
ρ=
ca cb c2 cd |10i
da db dc d2 |11i
h00| h01| h10| h11|
4.3. Редуцированные матрицы плотности 205
da db dc d2
если
1
|ψ1 i = √ (|0i + |1i) , |ψ2 i = |0i .
2
Решение. Для двумерного квантового состояния имеем
1 1
|Ψi = |ψ1 i ⊗ |ψ2 i = √ (|0i + |1i) ⊗ |0i = √ (|00i + |10i) .
2 2
Тогда по определению матрицы плотности, получим:
1 1
ρ = |Ψi hΨ| = √ (|00i + |10i) (h00| + h10|) √
2 2
1
= (|00i h00| + |00i h10| + |10i h00| + |10i h10|)
2
или
1 0 1 0
1 0 0 0 0
ρ= . N
2 1 0 1 0
0 0 0 0
Пример 4.15. Найти матрицу плотности ρ = |Ψi hΨ| кубита |Ψi = |ψ1 i ⊗ |ψ2 i,
если
1 √
|ψ1 i = |1i , |ψ2 i = |0i + 3 |1i .
2
Решение.
1 √
|Ψi = |10i + 3 |11i ,
2
1 √ √
ρ = |10i h10| + 3 |10i h11| + 3 |11i h10| + 3 |11i h11|
4
или
0 0 0 0
1 0 0 0 √0
ρ= . N
4 0 0 √
1 3
0 0 3 3
206 Глава 4. Квантовая информация
Задача 4. 6. Найти матрицу плотности ρ = |Ψi hΨ| кубита |Ψi = |ψ1 i ⊗ |ψ2 i,
если
1. √ p √ √ √
2 5− 5 5+1 3 1
|ψi = |0i + |1i , |ψ 0 i = |0i + |1i ;
4 4 2 2
2. p √ p √ √ p √
2+ 2 2− 2 0 2 5− 5
|ψi = |0i + |1i , |ψ i = |0i ;
2 2 4
3. p √ p √ √
2+ 2 2− 2 0 1 3
|ψi = |0i + |1i , |ψ i = |0i + |1i ;
2 2 2 2
4. √ √
3 1 0 1 3
|ψi = |0i + |1i , |ψ i = |0i + |1i .
2 2 2 2
ρ1 = Sp2 ρ, ρ2 = Sp1 ρ.
A00 A01 A02 A03
A10 A11 A12 A13
ρ=
A20
A21 A22 A23
A30 A31 A32 A33
редуцированные матрицы плотности можно вычислить по формулам
ρ1 = Sp2 ρ
+ (A00 + A11 ) |0i h0| + (A02 + A13 ) |0i h1|
+ (A20 + A31 ) |1i h0| + (A22 + A33 ) |1i h1| ;
208 Глава 4. Квантовая информация
A00 + A11 A02 + A13
ρ1 =
A20 + A31 A22 + A33
и
ρ2 = Sp1 ρ
= (A00 + A22 ) |0i h0| + (A01 + A23 ) |0i h1|
+ (A10 + A32 ) |1i h0| + (A11 + A33 ) |1i h1| ;
A00 + A22 A01 + A23
ρ2 = .
A10 + A32 A11 + A33
Пример 4.17. Найти редуцированные матрицы плотности пучка
1
ρ= (2 |00i h00| + 2 |00i h10| − 3 |10i h00| − 5 |11i h10|).
26
Решение. Перепишем ρ в виде
A00 A01 A02 A03 2 0 2 0
A10 A11 A12 A13
1 0 0
0 0
ρ= =
A20 A21 A22 A23 26 −3 0 0 0
A30 A31 A32 A33 0 0 −5 0
тогда
A00 + A11 A02 + A13 1 2+0 2+0 1 2 2
ρ1 = = =
A20 + A31 A22 + A33 26 −3 + 0 0+0 26 −3 0
A00 + A22 A01 + A23 1 2+0 0+0 1 2 0
ρ2 = = =
A10 + A32 A11 + A33 26 0 − 5 0+0 26 −5 0
или
1
ρ1 = (2 |0i h0| + 2 |0i h1| − 3 |1i h0|)
26
1
ρ2 = (2 |0i h0| − 5 |1i h0|). N
26
ρ1 = (a2 + b2 ) |0i h0| + (ac + bd) (|0i h1| + |1i h0|) + (c2 + d2 ) |1i h1| ,
ρ2 = (a2 + c2 ) |0i h0| + (ab + cd) (|0i h1| + |1i h0|) + (b2 + d2 ) |1i h1| .
Решение. Поскольку a = α, b = 0, c = β, d = 0, то
Для кубита Ψ ∈ H3 :
ρ1 = a20 + a21 + a22 + a23 |0i h0| + (a0 a4 + a1 a5 + a2 a6 + a3 a7 ) (|0i h1| + |1i h0|)
ρ2 = a20 + a21 + a24 + a25 |0i h0| + (a0 a2 + a1 a3 + a4 a6 + a5 a7 ) (|0i h1| + |1i h0|)
ρ3 = a20 + a22 + a24 + a26 |0i h0| + (a0 a1 + a2 a3 + a4 a5 + a6 a7 ) (|0i h1| + |1i h0|)
Здесь
1 i i
i 1 i
Rm =
1 + Hm , Rm = 1 − Hm ,
2 2
Hmi
- значение m-й базисной функции Хаара в точке i отрезка [0, 2k ].
Рассмотрим более подробно принципы построения данных выражений. Возмем
рекурсивную формулу для построения матриц Адамара
Hk Hk
Hk+1 = где H0 = 1.
Hk −Hk
Например
H0 H0 1 1
H0 = 1; H1 = = ;
H0 −H0 1 −1
1 1 1 1
H1 H1 1 −1 1 −1
H2 = = ;
H1 −H1 1 1 −1 −1
1 −1 −1 1
1 1 1 1 1 1 1 1
1 −1 1 −1 1 −1 1 −1
1
1 −1 −1 1 1 −1 −1
H2 H2 1 −1 −1 1 1 −1 −1 1
H3 = = ...
H2 −H2 1
1 1 1 −1 −1 −1 −1
1 −1 1 −1 −1 1 −1 1
1 1 −1 −1 −1 −1 1 1
1 −1 −1 1 −1 1 1 −1
Несложно изобразить функции Адамара графически. Например для H2 получим
dB dB
t
t
dB dB
t t
4.3. Редуцированные матрицы плотности 211
Преобразование Грея
Преобразование Грея - это перестановка элементов таблицы истинности булевой
функции таким образом, чтобы ее нижняя половина была симметрична верхней, за
исключением старшего бита, который просто инвертируется. Если разделить каждую
половину еще пополам, то свойство должно сохранятся для каждой половины и т.д.
F 2-битное преобразование
0 00 00 0
1 01 01 1
2 10 ⇒ 11 = 3
=
3 11 10 2
F 3-битное преобразование
0 000 000 0
1 001 001 1
2 010 011 3
3 011 010 2
= ⇒ =
4 100 110 6
5 101 111 7
6 110 101 5
7 111 100 4
Преобразование Грея числа B это его побитовое XOR со своим сдвинутым вправо
значением:
Gi = Gray(Bi) = Bi ⊕ Bi+1
F
100
Gray(4) = Gray(1002) = 010 = 1102 = 6
110
F
1101
Gray(13) = Gray(11012) = 0110 = 10112 = 11
1011
Обратный алгоритм – преобразование кода Грея в двоичный код – можно выра-
зить рекуррентной формулой
Bi = Bi+1 ⊕ Gi+1
F
110
011
G−1 (6) = G−1 (1102 ) =
001 = 1002 = 4
100
212 Глава 4. Квантовая информация
F
1011
0101
−1 −1
G (11) = G (10112 ) =
0010 = 11012 = 13
0001
1101
Преобразование Уолша
Функциями Уолша назвывается семейство функций, образующих ортогональную
систему, принимающих значения только 1 и -1 на всей области определения.
√
trA ± tr 2 A − 4∆
λ0,1 = ,
2
где trA = a00 + a11 след матрицы, а ∆ = a00 a11 − a01 a10 ее определитель, квантовое
состояние |Ψi можно записать в виде
где
1 серия
1
|x0 i = q (a01 |0i + (λ0 − a00 ) |1i)
a201 + (λ0 − a00 )2
1
|y0 i = q ((λ1 − a00 ) |0i − a01 |1i)
2 2
a01 + (λ1 − a00 )
1
|x1 i = q (a01 |0i + (λ1 − a00 ) |1i)
a201 + (λ1 − a00 )2
214 Глава 4. Квантовая информация
1
|y1 i = q (−(λ0 − a00 ) |0i + a01 |1i)
a201 + (λ0 − a00 )2
Однако на практике данными формулами пользоваться бывает не удобно, по-
скольку они приводят к возникновению неопределенностей типа 0/0 в коэффициен-
тах из за выбора способа нормировки собственных векторов. Поэтому приходится
искать другие комбинации решений, приводящих к ненулевым собственнным векто-
рам. Для (2×2) матриц возможны 4 различных комбинации построения собственных
векторов. Одну из них мы рассмотрели, а остальные приведены ниже.
2 серия
1
|x0 i = p 2 ((λ0 − a11 ) |0i + a10 |1i)
a10 + (λ0 − a11 )2
1
|y0 i = q (−a10 |0i + (λ1 − a11 ) |1i)
2
a210 + (λ1 − a11 )
1
|x1 i = q ((λ1 − a11 ) |0i + a10 |1i)
2 2
a10 + (λ1 − a11 )
1
|y1 i = q (a10 |0i − (λ0 − a11 ) |1i)
2 2
a10 + (λ0 − a11 )
3 серия
1
|x0 i = p 2 (a01 |0i + (λ0 − a00 ) |1i)
a01 + (λ0 − a00 )2
1
|y0 i = q (a10 |0i − (λ1 − a11 ) |1i)
a210 + (λ1 − a11 )2
1
|x1 i = q ((λ1 − a11 ) |0i + a10 |1i)
a210 + (λ1 − a11 )2
1
|y1 i = q ((a00 − λ0 ) |0i + a10 |1i)
a201 + (λ0 − a00 )2
4 серия
1
|x0 i = p 2 ((a11 − λ0 ) |0i − a10 |1i)
a10 + (λ0 − a11 )2
1
|y0 i = q ((λ1 − a00 ) |0i − a01 |1i)
a201 + (λ1 − a00 )2
1
|x1 i = q (a01 |0i + (λ1 − a00 ) |1i)
a201 + (λ1 − a00 )2
4.4. Разложение Шмидта 215
1
|y1 i = q (a10 |0i − (λ0 − a11 ) |1i)
a210 + (λ0 − a11 )2
1
|y0 i = q ((λ1 − a00 ) |0i − a01 |1i)
a201 + (λ1 − a00 )2
1
= p ((1 + x − 1) |0i − x |1i)
x + (1 + x − 1)2
2
1
= √ (|0i − |1i) ,
2
1
|x1 i = q (a01 |0i + (λ1 − a00 ) |1i)
a201 + (λ1 − a00 )2
1
= p (x |0i + (1 + x − 1) |1i)
x2 + (1 + x − 1)2
1
= √ (|0i + |1i) ,
2
216 Глава 4. Квантовая информация
1
|y1 i = q (−(λ0 − a00 ) |0i + a01 |1i)
2
a201 + (λ0 − a00 )
1
= p (−(1 − x − 1) |0i + x |1i)
x2 + (1 − x − 1)2
1
= √ (|0i + |1i) .
2
1
с учетом нормировки √ записывается в виде
2 + 2x2
1−x 1+x
|Ψi = √ |x0 y0 i + √ |x1 y1 i ,
2 + 2x2 2 + 2x2
где
1 1
|x0 i = |y0 i = √ (|0i − |1i) , |x1 i = |y1 i = √ (|0i − |1i) . N
2 2
1
|Ψi = √ (|00i + 2 |10i − 3 |11i).
14
1−λ 0
=0 или (1 − λ)(−3 − λ) − 2 · 0 = 0.
2 −3 − λ
λ0 = −3, λ1 = 1.
1
|x0 i = p ((λ0 − a11 ) |0i + a10 |1i)
a210 + (λ0 − a11 )2
1
= p ((−3 + 3) |0i + 2 |1i) = |1i
2 + (−3 + 3)2
2
1
|y0 i = q (−a10 |0i + (λ1 − a11 ) |1i)
2 2
a10 + (λ1 − a11 )
1 1
= p (−2 |0i + (1 + 3) |1i) = √ (− |0i + 2 |1i)
22 + (1 + 3)2 5
1
|x1 i = q ((λ1 − a11 ) |0i + a10 |1i)
a210 + (λ1 − a11 )2
1 1
= p ((1 + 3) |0i + 2 |1i) = √ (2 |0i + |1i)
2
2 + (1 + 3) 2 5
1
|y1 i = q (a10 |0i − (λ0 − a11 ) |1i)
2 2
a10 + (λ0 − a11 )
1
= p (2 |0i − (−3 + 3) |1i) = |0i
22 + (−3 + 3)2
Очевидно, для того чтобы состояние |Ψi было сепарабельным необходимо и доста-
точно, чтобы одно из собственных значений λ0,1 было равно нулю (например λ1 = 0),
тогда |Ψi = λ0 |ψ0 ϕ0 i.
Математически квантовый оператор, позволяющий запутать два кубита |xi и |yi
называется оператором CNOT (Controlled NOT) и дается выражением:
Вход Выход
|xi |yi |xi |x ⊕ yi
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0
H123
P12 ψ1
ψ1
ψ2
ψ2 +
ψ3 +
с таблицей истинности
Вход Выход
|xi |yi |zi |xi |yi |x&y ⊕ zi
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0
π π
1. |ψ1 i = R |0i и |ψ2 i = R |0i ,
2
π 3
π
2. |ψ1 i = R |0i и |ψ2 i = R |0i ,
3
π 4
π
3. |ψ1 i = R |0i и |ψ2 i = R |0i ,
4
π 6
π
4. |ψ1 i = R |0i и |ψ2 i = R |0i .
6 3
222 Глава 4. Квантовая информация
Вход Выход
x f1 (x) f2 (x) f3 (x) f4 (x)
0 0 1 0 1
1 0 1 1 0
1 0 0 0 0 0 0 1
0 1 0 0 0 0 1 0
U1 =
0
, U2 = ,
0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
0 1 0 0 0 0 1 0
1 0 0 0 0 0 0 1
U3 =
0
, U4 = .
0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1
U1 √ (|00i + |11i) √ (|00i + |11i) √ (|00i + |10i) |00i
2 2 2
1 1
U2 √ (|00i + |11i) √1 (|11i
2
+ |00i) √ (|10i + |00i) |00i
2 2
1 1 1
U3 √ (|00i + |11i) √ (|10i + |01i) √ (|11i + |01i) |01i
2 2 2
1 1 1
U4 √ (|00i + |11i) √ (|01i + |10i) √ (|01i + |11i) |01i
2 2 2
224 Глава 4. Квантовая информация
1 1 1
U1 √ (|00i − |11i) √ (|00i − |11i) √ (|00i − |10i) |10i
2 2 2
1 1
U2 √ (|00i − |11i) √1 (|11i
2
+ |00i) √ (|10i − |00i) − |10i
2 2
1 1 1
U3 √ (|00i − |11i) √ (|10i + |01i) √ (|11i − |01i) − |11i
2 2 2
1 1 1
U4 √ (|00i − |11i) √ (|01i + |10i) √ (|01i − |11i) |11i
2 2 2
P12 P12
x H H x
Ui
0 + + z
1
0 ψ0 = (I ⊗ I) ψ0 √ (|00i + |11i)
2
1
1 ψ1 = (X ⊗ I) ψ0 √ (|10i + |01i)
2
1
2 ψ2 = (Y ⊗ I) ψ0 √ (− |10i + |01i)
2
1
3 ψ3 = (Z ⊗ I) ψ0 √ (|00i − |11i)
2
1 1 1
0 √ (|00i + |11i) √ (|00i + |10i) √ (|0i + |1i) |0i
2 2 2
1 1 1
1 √ (|10i + |01i) √ (|11i + |01i) √ (|1i + |0i) |1i
2 2 2
1 1 1
2 √ (− |10i + |01i) √ (− |11i + |01i) √ (− |1i + |0i) |1i
2 2 2
1 1 1
3 √ (|00i − |11i) √ (|00i − |10i) √ (|0i − |1i) |0i
2 2 2
1 1 1 1
1 √ (|1i + |0i) √ √ (|0i − |1i) + √ (|0i + |1i) |0i |1i
2 2 2 2
1 1 1 1
2 √ (− |1i + |0i) √ − √ (|0i − |1i) + √ (|0i + |1i) |1i |1i
2 2 2 2
1 1 1 1
3 √ (|0i − |1i) √ √ (|0i + |1i) − √ (|0i − |1i) |1i |0i
2 2 2 2
4.6. Квантовые алгоритмы 227
Например, для передачи значения «3» отправитель кодирует свою часть Ш-забита
Z-преобразованием и передает получателю. Получатель действует на Ш-забит сна-
чала CNOT оператором, затем оператором Адамара. Полученное состояние получа-
тель подвергает измерению. Пусть измерительное устройство настроено на проеци-
рование входящего кубита на состояние
|ψΠ i = |0i ,
Такой результат говорит, что состояние кубита и измеряющего устройства были ор-
тогональны. Мы потеряли 1 кубит (он был поглощен измерительным устройством),
однако мы получили 1 bit классической информации: оказывается кубит был в со-
стоянии |1i. Измеряя второй кубит тем же измерительным устройством получим
0 H X H
out
ψ
0 + +
0 + +
и Ш-забита:
1
|Ψi = |φi ⊗ |ψi = √ (a |000i + a |011i + b |100i + b |111i) .
2
Действуя на первые два свои кубита CNOT операцией, а затем оператором Адамара
на первый кубит отправитель получает состояние
1
Ψout = H1 P12 Ψin 123 = √ H1 (a |000i + a |011i + b |110i + b |101i)
2
1 |00i (a |0i + b |1i) + |10i (a |0i − b |1i) +
=
2 |01i (a |1i + b |0i) + |11i (a |1i − b |0i)
ψ H
0 H +
0 + X ψ
230 Глава 4. Квантовая информация
E = X ⊗ I ⊗ I.
S|e1 , e2 , e3 i → |e1 , e1 ⊕ e2 , e1 ⊕ e3 i
0
T321
out 1 √ √
ψ = √ |100i + |011i + 3|001i + 3|110i .
2 2
1 √ √
|ψ0 i ⊗ |z1 z2 i = T231 P12 P13 √ |100i + |011i + 3 |001i + 3 |110i
2 2
1 √ √
= T231 P12 √ |101i + |011i + 3 |001i + 3 |111i
2 2
1 √ √
= T231 √ |111i + |011i + 3 |001i + 3 |101i
2 2
1 √ √
= √ |011i + |111i + 3 |001i + 3 |101i
2 2
1 1 √ √
= √ (|011i + |111i) + √ 3 |001i + 3 |101i
2 2 2 2
√
1 3
= √ (|0i + |1i) ⊗ |11i + √ (|0i + |1i) ⊗ |01i
2 2 2 2
√
1 1 3 1
= √ (|0i + |1i) ⊗ |11i + √ (|0i + |1i) ⊗ |01i
2 2 2 2
√ !
1 1 3
= √ (|0i + |1i) ⊗ |11i + |01i = |ψ0 i ⊗ |z1 z2 i
2 2 2
4.8. Клонирование квантовой информации 233
U|ϕi|0i = |ϕi|ϕi.
ρout 2 2
1,2 = α |0ih0| + β |1ih1|.
и выходного
ρout = α2 |0ih0| + β 2 |1ih1|
кубитов, нетрудно видеть, что оператор плотности выходного состояния выражается
через оператор плотности входа следующим образом:
1 in 1 in
ρout
1,2 = ρ0 + ρ3 .
2 2
Здесь
ρ3 = |ψ3 ihψ3 | = α2 |0ih0| − αβ|0ih1| − αβ|1ih0| + β|1ih1|,
|ψ3 i = σ3 |ψ0 i = α|0i − β|1i.
4.8. Клонирование квантовой информации 235
hψ0 | ψ3 i = α2 − β 2 6= 0,
т.е. состояния не ортогональны, а это означает, что волновые функции |ψ0 i и |ψ3 i пе-
рекрываются и часть информации относительно |ψ0 i содержится в матрице плотно-
сти ρin
3 . Поэтому для вычисления степени перекрытия волновых состояний вводится
понятие точности копирования
F = hψ0 |ρout 4 4
1,2 |ψ0 i = α + β .
[3] Вентцель Е.С., Овчаров Л.А. Теория вероятностей. М.:Наука, 1969. - 368 с.
[4] Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные
понятия. М.:МЦНМО, 2003. - 504 с.
237
238 Литература
[15] Wootters W.K. and Zurek W.H. A Single Quantum Cannot be Cloned, Nature,
1982, V.299, pp. 802-803.
.