Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова

• Название: Лекции по теории информации под редакцией Н. А. Кузнецова
• Анкор: Лекции по теории информации
• Дата: 17.04.2022
• Размер: 1.32 Mb.
• Имя файла: Фурсов teoria_informacii.pdf
• Тип: Лекции; #480820
• страница: 9 из 16

A
Максимально возможное число кодовых комбинаций простого двоичного кода max
2
n
N

. Ниже приводятся используемые далее по тексту правила сложения, умножения и сложения по модулю (

) в двоичной системе.
Сложение
0 1
0 0
1 1
1 10
Умножение
0 1
0 0
0 1
0 1
Сложение по модулю
0 1
0 0
1 1
1 0
Помимо двоичной системы получили распространение системы с основа- нием, равным целой степени двойки (восьмеричная, шестнадцатиричная), кото- рые легко сводятся как к двоичной, так и к десятичной, но дают более компакт- ную запись. Например, в восьмеричной системе каждой из восьми цифр (0-7) ставится в соответствие трехразрядное двоичное число. В шестнадцатиричной системе перевод чисел в двоичную осуществляется путем замены каждой ше- стнадцатиричной цифры четырехразрядным двоичным числом.

77
Используются также двоично-десятичные коды, в которых каждую цифру десятичного числа записывают в виде четырехразрядного двоичного числа.
Этот код относится к числу взвешенных кодов. Для фиксации цифр десятично- го числа наибольшее практическое применение нашли коды 8-4-2-1; 7-4-2-1; 5-
1-2-1 и 2-4-2-1. Цифры в названии кода выражают веса единиц в соответст- вующих разрядах.
При некоторых способах кодирования непрерывных сообщений (напри- мер, при преобразовании угла поворота диска с нанесенной на него маской в двоичный код) источником больших ошибок может быть одновременное изме- нение цифр в нескольких разрядах. Например, в простом двоичном коде одно- временное изменение цифр в четырех разрядах имеет место при переходе от изображения (маски) цифры 7 к маске цифры 8. Для устранения этого явления используют специальные двоичные коды, у которых при переходе от изобра- жения одного числа к изображению следующего соседнего числа изменяется значение цифры только одного разряда. При этом ошибка неоднозначности считывания не превышает единицы младшего разряда. К числу таких кодов от- носится код Грея.
9.2 Основная теорема Шеннона о кодировании
для канала без помех
Эффективное кодирование сообщений, минимизирующее среднее число символов, требуемых для представления одного знака сообщения, опирается на следующую теорему (Шеннона):
1) при любой производительности источника сообщений, меньшей пропускной способности канала:
( )
д
I Z
C


, существует способ коди- рования, позволяющий передавать по каналу все сообщения, выраба- тываемые источником;
2) не существует способа кодирования, обеспечивающего передачу со- общений без их неограниченного накопления, если
( )
д
I Z
C



78
Справедливость теоремы покажем, опираясь на свойство асимптотической рав- номерности.
Пусть количество знаков в последовательности равно N, а энтропия источ- ника
 
H Z
. Предположим также, что длина сообщения T велика и все сооб- щения являются типичными. Тогда для этих последовательностей выполняется неравенство (7.1):
1 1
log
( )
H Z
N
p










,
0 0



, а число типичных последовательностей
1
T
N
p

в соответствии с ним будет
 
 
 
2 2
2
и
T
H Z
NH Z
TI Z
T
N





(9.2)
Здесь предполагается, что средняя длительность знака
и

известна, поэтому
и
N
T


и по определению
 
 
и
I Z
H Z



Предположим, что кодирование осуществляется с использованием алфави- та объемом
m
. Тогда с учетом того, что пропускная способность дискретного канала


2
log
д
к
C
m


, число последовательностей длительности T (с числом знаков
к
N
T


), пропускаемых каналом, определится как:
2 2
log log
2 2
2
k
k
k
д
T
T
m
m
T
TC
N
k
N
m
m








(9.3)
Сравнивая (9.2) и (9.3) нетрудно заметить, что если
( )
д
I Z
C


, то имеет ме- сто неравенство
k
T
N
N

. Это означает, что число последовательностей, про- пускаемых каналом, достаточно, чтобы закодировать все типичные последова- тельности знаков. Вероятность появления нетипичных последовательностей при
N  
стремится к 0, что и доказывает первую часть теоремы.
Справедливость второй части теоремы, указывающей на невозможность осуществить передачу при
( )
д
I Z
C


, следует из определения пропускной спо- собности канала, как максимально достижимой скорости передачи информа- ции. Поэтому в данном случае неизбежно накопление на передающей стороне.

79
9.3 Методы эффективного кодирования некоррелированной
последовательности знаков, код Шеннона-Фано
Теорема Шеннона отвечает на вопрос: при каких условиях возможно в принципе построение кода, обеспечивающего передачу всех сообщений, фор- мируемых источником. Естественно стремление строить наилучшие, с точки зрения максимума передаваемой информации, коды. Для того чтобы каждый символ (например, двоичного) кода нес максимум информации, символы кодо- вой комбинации должны быть независимы и принимать значения (0 и 1) с рав- ными вероятностями. Построение эффективных кодов в случае статистиче-
ской независимости символов сообщений опирается на методики Шеннона и
Фано (код Шеннона-Фано).
Код строится следующим образом. Кодируемые знаки выписывают в таб- лицу в порядке убывания их вероятностей в сообщениях. Затем их разделяют на две группы так, чтобы значения сумм вероятностей в каждой группе были близкими. Все знаки одной из групп в соответствующем разряде кодируются, например, единицей, тогда знаки второй группы кодируются нулем. Каждую полученную в процессе деления группу подвергают вышеописанной операции до тех пор, пока в результате очередного деления в каждой группе не останется по одному знаку (таблица 9.1).
В приведенном примере среднее число символов на один знак
8 7
7 1
1 7
127 2
2 64
ср
i i
i
i
i
i
l
p l








, где
i
l – число символов в i -м разряде, имеет такую же величину, как и энтро- пия, рассчитанная в среднем на один знак:
8 7
7 2
2 2
7 1
1 1
1 127
( )
log log 2
log 2 2
2 64
i
i
i
i
i
i
H z
p
p






 
 








Таблица 9.1
Знаки
Вероятности
Коды
1
z
1/2 1
2
z
1/4 01

80 3
z
1/8 001 4
z
1/16 0001 5
z
1/32 00001 6
z
1/64 000001 7
z
1/128 0000001 8
z
1/128 0000000
Совпадение результатов связано с тем, что вероятности знаков являются целочисленными отрицательными степенями двойки. В общем случае
( )
ср
l
H z

Если величина среднего числа символов на знак оказывается значительно большей, чем энтропия, то это говорит об избыточности кода. Эту избыточ- ность можно устранить, если перейти к кодированию блоками. Рассмотрим простой пример кодирования двумя знаками
1 2
,
z z с вероятностями их появле- ния в сообщениях 0,1 и 0,9 соответственно.
Если один из этих знаков кодировать, например, нулем, а другой единицей, т.е. по одному символу на знак, имеем соответственно
0,1 1 0,9 1
ср
l 
 
 
1,0,
2 2
( )
0,1 log 0,1 0,9 log 0,9
H z  



=0,47.
При переходе к кодированию блоками по два знака (таблица 9.2)


,
1 0,81 1 0,09 2 0, 09 3 0, 01 3 0, 645 2
2
ср бл
ср
l
l 

 
 
 


Таблица 9.2
Блоки
Вероятности
Коды
1
z
1
z
0,81 1
2
z
1
z
0,09 01 1
z
2
z
0,09 001 2
z
2
z
0,01 000
Можно проверить, что при кодировании блоками по три символа среднее число символов на знак уменьшается и оказывается равным около 0,53.

81
Эффект достигается за счет того, что при укрупнении блоков, группы можно делить на более близкие по значениям суммарных вероятностей под- группы. Вообще lim
( )
ср
n
l
H z


, где
n
– число символов в блоке.
9.4 Методика кодирования Хаффмана
Рассмотренная выше методика кодирования не всегда приводит к хороше- му результату, вследствие отсутствия четких рекомендаций относительно того, как делить множество кодируемых знаков на подгруппы. Рассмотрим методику кодирования Хаффмана, которая свободна от этого недостатка.
Кодируемые знаки, также как при использовании метода Шеннона-Фано, располагают в порядке убывания их вероятностей (таблица 9.3). Далее на каж- дом этапе две последние позиции списка заменяются одной и ей приписывают вероятность, равную сумме вероятностей заменяемых позиций. После этого производится пересортировка списка по убыванию вероятностей, с сохранени- ем информации о том, какие именно знаки объединялись на каждом этапе. Про- цесс продолжается до тех пор, пока не останется единственная позиция с веро- ятностью, равной 1.
Таблица 9.3
Вспомогательные столбцы
Знаки
i
p
1 2
3 4
5 6
7 1
z
0,22 0,22 0,22 0,26 0,32 0,42
0,58
0,1
2
z
0,2 0,2 0,2 0,22 0,26
0,32
0,42
3
z
0,16 0,16 0,16 0,2
0,22
0,26
4
z
0,16 0,16 0,16
0,16
0,2
5
z
0,1 0,1
0,16
0,16
6
z
0,1
0,1
0,1
7
z
0,04
0,06
8
z
0,02
После этого строится кодовое дерево. Корню дерева ставится в соответст- вие узел с вероятностью, равной 1. Далее каждому узлу приписываются два по- томка с вероятностями, которые участвовали в формировании значения вероят-

82 ности обрабатываемого узла. Так продолжают до достижения узлов, соответст- вующих вероятностям исходных знаков.
Процесс кодирования по кодовому дереву осуществляется следующим об- разом. Одной из ветвей, выходящей из каждого узла, например, с более высо- кой вероятностью, ставится в соответствие символ 1, а с меньшей – 0. Спуск от корня к нужному знаку дает код этого знака. Правило кодирования в случае равных вероятностей оговаривается особо. Таблицы 9.3, 9.4 и рисунок 9.1 ил- люстрируют применение методики Хаффмана. Жирным шрифтом в таблице 9.3 выделены объединяемые позиции, подчеркиванием – получаемые при объеди- нении позиции.
Таблица 9.4
Знаки
Коды
1
z
01 2
z
00 3
z
111 4
z
110 5
z
100 6
z
1011 7
z
10101 8
z
10100
Рис. 9.1. Кодовое дерево
Замечательным свойством кодов, построенных с применением методик
Шеннона-Фано или Хаффмана, является их префиксность. Оно заключается в том, что ни одна комбинация кода не является началом другой, более длинной комбинации. Это позволяет при отсутствии ошибок осуществлять однозначное декодирование ряда следующих друг за другом кодовых комбинаций, между которыми отсутствуют разделительные символы.

83
9.5 Методы эффективного кодирования коррелированной
последовательности знаков
Ранее было показано, что повышение производительности источников и каналов достигается путем формирования и передачи шумоподобных сигналов
(символы независимы друг от друга и равномерно распределены). Это свойство может не соблюдаться, если знаки в сообщениях коррелированны. Для повы- шения эффективности кодирования коррелированной последовательности ис- кусственно производят декорреляцию.
Один из способов заключается в укрупнении алфавита знаков. При этом передаваемые сообщения разбиваются на двух-, трех- или
n
- знаковые сочета- ния (непересекающиеся блоки), вероятности которых известны. Каждое соче- тание кодируется одним из описанных выше способов:
1 1 3 4 1 2 3 1 2 4 1 3
n
n
z z z
z z z z z z
z z z


 


При увеличении числа знаков в сочетаниях корреляция знаков в сообщении уменьшается. Однако при этом возрастает задержка в передаче сигналов на время формирования сочетаний.
От этого недостатка в некоторой степени свободен метод, в котором каж- дое сочетание из
l
знаков (
l
-грамма) формируется путем добавления текущего знака сообщения и отбрасывания последнего знака
l
-граммы:
2-я
l
-грамма
1 3 2 4 2 1 3 1 2
z z z
z z z z z z
1-я
l
-грамма
Сочетание из двух знаков называют диграммой, из трех – триграммой и т.д.
В процессе кодирования
l
-грамма непрерывно перемещается по тексту со- общения, а кодовое обозначение каждого знака сообщения зависит от
1
l 
предшествующих знаков и может быть определено с использованием методик
Шеннона-Фано или Хаффмана. Задержка сигнала в данном случае имеет место лишь на начальном этапе формирования первой
l
-граммы.

84
9.6 Недостатки методов эффективного кодирования
1. Различия в длине кодовых комбинаций. Обычно знаки на вход устройства кодирования поступают через равные промежутки времени. Если им соответст- вуют комбинации различной длины, то для обеспечения полной загрузки кана- ла при передаче без потерь необходимо предусмотреть буферное устройство, как на передающей, так и на приемной стороне.
2. Задержка в передаче информации. Как было показано, достоинства эф- фективного кодирования проявляются в полной мере при кодировании длин- ными блоками. Для этого необходимо накапливать знаки, как при кодировании, так и при декодировании, что приводит к значительным задержкам.
3. Низкая помехозащищенность. Даже одиночная ошибка, возникшая в процессе передачи, может нарушить свойство префиксности кода и повлечь за собой неправильное декодирование ряда последующих комбинаций. Это явле- ние называют треком ошибки.
4. Сложность технической реализации. Использование буферных уст- ройств, для обеспечения равномерной загрузки канала, при разной длине кодо- вых комбинаций и организация кодирования блоками для повышения эффек- тивности приводят к усложнению реализации систем эффективного кодирова- ния. Если вдобавок применяются некоторые аппаратные решения, обеспечи- вающие повышение помехозащищенности, то все это в совокупности может свести на нет основное достоинство систем эффективного кодирования, связан- ное с тем, что знаки, имеющие большую вероятность, кодируются более корот- кими кодовыми словами.

85
Лекция 10
Введение в теорию помехоустойчивого кодирования
10.1 Теорема Шеннона о кодировании для канала с помехами
Теоретической основой помехоустойчивого кодирования является сле- дующая теорема (Шеннона):
1) при любой производительности источника меньшей, чем пропускная спо- собность канала, существует способ кодирования, который позволяет обеспечить передачу всей информации от источника со сколь угодно малой вероятностью ошибки;
2) не существует способа кодирования, позволяющего вести передачу ин- формации со сколь угодно малой вероятностью ошибки, если производи- тельность источника больше пропускной способности канала.
Доказательство. Пусть источник генерирует типичные (разрешенные) по- следовательности большой длительности T , с числом символов
и
N
T


, где
и

– среднее время формирования одного символа. Тогда справедливо неравен- ство (7.1), а число типичных последовательностей в соответствии с (9.2)
 
 
 
2 2
и
T
H Z
NH Z
T
N
Z



(10.1)
Если предположить, что последовательности формируются из символов алфавита объемом
m
так, что символы статистически независимы, то общее число возможных последовательностей длительности T , которые могут быть в принципе сформированы на входе канала
 
2 2
log log
2 2
k
T
m
N
m
N
N Z
m




,
(10.2) где
k

– среднее время передачи одного символа по каналу связи.
Пусть выполняется условие первой части теоремы – пропускная способ- ность канала больше производительности источника:
 
 
д
и
C
I Z
H Z




(10.3)
В соответствии с (8.6) пропускная способность дискретного канала

86
 
 
 
( )
2
( )
max log
( , )
max
V
p z
V
д
p z
k
k
k
H Z
H
Z
m
H
Z
I Z V
С








(10.4)
Подставляя правую часть (10.4) в левую часть неравенства (10.3) имеем
2
log
( )
( )
V
к
и
m
H
Z
H Z




Ничего не изменится, если умножить обе части последнего равенства на T :


2
log
( )
( )
V
к
и
T
T
m
H
Z
H Z




(10.5)
Поскольку условная энтропия
( )
0
V
H
Z  , при ее отбрасывании неравенст- во (10.5) только усилится:
2
log
( )
к
и
T
T
m
H Z



Нетрудно заметить, что левая и правая части последнего неравенства суть пока- затели степени в (10.1) и (10.2), следовательно, в силу свойства степеней
2
( )
log
2 2
и
к
T
T
H Z
m



, откуда следует
 
 
T
N Z
N
Z

(10.6)
Это означает, что существует
 
 
T
N
Z
N Z
C
различных способов кодирования, по- зволяющих каждой типичной последовательности поставить в соответствие по- следовательность из множества
 
N Z
. При равновероятном выборе последова- тельностей из этого множества вероятность
p
того, что данная последователь- ность окажется разрешенной
2 2
( )
log log
( )
( )
2 1
( )
2 2
и
к
к
и
H Z
T
T
m
m H Z
T
T
N Z
p
N Z














(10.7)
При получении на выходе канала конкретной последовательности
v
оста- ется неопределенность относительно переданной последовательности
z
, свя-

87 занная с
( )
V
H
Z , которая определяется уровнем шумов в канале. Эта неопреде- ленность эквивалентна неопределенности выбора из
 


 
2
k
V
T
H
Z
V
N
Z


(10.8) последовательностей. Заметим, что соотношение (10.8) может быть получено по аналогии с (10.1).
Конкретная последовательность может быть идентифицирована со сколь угодно малой вероятностью ошибки, если среди
 
V
N
Z
последовательностей она оказалась единственной разрешенной. Отсюда, в частности, следует, что любой способ кодирования и декодирования должен заключаться в разбиении всего множества последовательностей на подмножества, каждое из которых со- держит лишь одну разрешенную.
Оценим среднюю по всем возможным способам кодирования вероятность
p
того, что ни одна из
 
1
V
N
Z 
последовательностей не является разрешен- ной:


 
1 1
V
N
Z
p
p



(10.9)
Здесь
p
– вероятность (10.7) того, что данная последовательность разрешенная.
Поскольку


1 1
p


, вместо равенства (10.9) можно записать неравенство


 
1
V
N
Z
p
p


(10.10)
Разложим правую часть (10.10) в ряд Тейлора в окрестности
0
p 
:


 
 
 
 


2 1
1 1
1 2
V
N
Z
V
V
V
p
N
Z p
N
Z
N
Z
p

 



Можно показать, что члены этого ряда убывают по абсолютной величине. По признаку Лейбница, если ряд знакопеременный и члены убывают по абсолют- ной величине, то величина остатка не превышает величину первого отбрасы- ваемого члена и имеет с ним одинаковый знак.
Таким образом, если ограничиться двумя первыми членами, неравенство
(10.10) только усилится:
 
1
V
p
N
Z p
 
,
(10.11)

88 где
p
– вероятность, определяемая в (10.7). Прежде чем осуществить ее замену в (10.11), несколько преобразуем (10.7). Для этого воспользуемся неравенством
(10.5), которое представим в виде
2
log
( )
( )
V
к
и
к
T
T
T
m
H Z
H
Z





(10.12)
Добавив в правую часть (10.12) некоторое положительное число

это неравен- ство превратим в равенство:
2
log
( )
( )
V
к
и
к
m
H Z
H
Z
T
T



















(10.13)
Наконец, заменив показатель степени двойки в (10.7) правой частью из (10.13) получим:
 
( )
( )
1 1
1 2
2 2
2
V
V
к
к
TH
Z
T
H
Z
T
V
T
p
N
Z
















(10.14)
Подставив полученное значение вероятности
p
в (10.11), получаем
1 1
2
T
p

 
(10.15)
Напомним, что
p
– вероятность того, что ни одна из
 
1
V
N
Z 
не является разрешенной (следовательно, одна из
 
V
N
Z
последовательностей является разрешенной). Тогда вероятность ошибки:
1 2
T
ош
p
p


 

(10.16)
Из (10.16) видно, что
0
ош
p
 при
T  
. Таким образом, всегда можно по- добрать длину последовательности такую, что средняя вероятность ошибки окажется сколь угодно малой по всем способам кодирования. Вторую часть теоремы примем без доказательства.
Теорема имеет важное теоретическое значение. Хотя в ней не объясняется, как строить коды, она обосновывает принципиальную возможность построения кодов, обеспечивающих передачу с как угодно высокой точностью. Теорема опровергает интуитивно казавшееся правильным предположение, что безоши- бочная передача в канале с помехами невозможна. Из (10.16) следует, что при

89 безграничном увеличении длительности T сообщений может быть достигнута как угодно высокая точность передачи. Конечно, безошибочная передача при наличии помех возможна лишь теоретически, т.к. нельзя безгранично увеличи- вать длительность кодируемой последовательности.