Информатика -продвинутый курс



         

ПОНЯТИЕ О ТЕОРЕМАХ ШЕННОНА - часть 3


т.е. код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.

Таблица 1.8 Пример к первой теореме Шеннона

N

Рхi

xi

Код

ni

пi- • Рi

Рхi • log Рхi

1

0,19

X1

10

2

0,38

-4,5522

2

0,16

X2

001

3

0,48

-4,2301

3

0.16

X3

011

3

0,48

-4,2301

4

0,15

X4

101

3

0,45

-4,1054

5

0,12

X5

111

3

0,36

-3,6706

6

0,11

X6

111

3

0,33

- 3,5028

7

0,09

X7

1011

4

0,36

-3,1265

8

0,02

X8

1001

4

0,08

-3,1288

?=1

                                                              ?=2,92

?=2,85

Вторая теорема Шеннона

гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. Таким образом, вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если скорость создания сообщений меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу со сколь угодно мглой частотой ошибок.

Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность Х

= {xi} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины п

вводится r символов и по каналу передается новая последовательность из п + r

символов. Число возможных последовательностей длины и + т больше числа возможных последовательностей длины п.

Множество всех последовательностей длины п

+ r может быть разбито на п подмножеств, каждому из которых сопоставлена одна из последовательностей длины п.

При наличии помехи на последовательность из п

+ r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.

Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины п + r, и тем самым восстановить исходную последовательность длины п.

Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой проблемы.




Содержание  Назад  Вперед