48742 (Расчет оптимального кода по методике Шеннона-Фано), страница 2

2016-07-30СтудИзба

Описание файла

Документ из архива "Расчет оптимального кода по методике Шеннона-Фано", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "48742"

Текст 2 страницы из документа "48742"

дв. симв.

Однако эту цифру необходимо округлить до ближайшего целого числа (в большую сторону), так как длина кода не может быть выражена дробным числом.

В общем случае, избыточность от округления:

где , k - округленное до ближайшего целого числа значение . Для нашего примера

Избыточность необходима для повышения помехоустойчивости кодов и ее вводят искусственно в виде добавочных символов. Если в коде всего n разрядов и из них несут информационную нагрузку, то характеризуют абсолютную корректирующую избыточность, а величина характеризует относительную корректирующую избыточность.

Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:

1) множество из сообщений располагается в порядке убывания вероятностей;

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

Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (нижней подгруппе);

3) первой группе присваивается символ 0, а второй группе - символ 1;

4) каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны;

5) первым группам каждой из подгрупп вновь присваивается 0, а вторым - 1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.

Построенный код называют оптимальным неравномерным кодом (ОНК).

ПРАКТИЧЕСКАЯ ЧАСТЬ

a) Расчеты

  1. рассчитывается первоначальные вероятности для неравновероятных символов алфавита.

  2. выполняет нормирование указанных вероятностей.

  3. рассчитывается энтропия алфавита из равновероятных символов.

  4. производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.

  5. с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.

  6. строится оптимальный код по методу Шеннона-Фано.

Расчет вероятностей.

Промежуточные значения:

k-1

...pk = S pn /(m - k + 1).

n-1

Окончательный результат:

рi = pi/( pi)

p1 = 0,1500

p2 = 0,0065

p3 = 0,0071

p4 = 0,0078

p5 = 0,0086

p6 = 0,0095

p7 = 0,0105

p8 = 0,0118

p9 = 0,0132

p10 = 0,0150

p11 = 0,0171

p12 = 0,0198

p13 = 0,0231

p14 = 0,0273

p15 = 0,0327

p16 = 0,0400

p17 = 0,0500

p18 = 0,0643

p19 = 0,0857

p20 = 0,1200

p21 = 0,1800

p22 = 0,3000

p23 = 0,6000

p24 = 1,8000

рi = 3,6

p1=0,0417

p2=0,0018

p3=0,0020

p4=0,0022

p5=0,0024

p6=0,0026

p7=0,0029

p8=0,0033

p9=0,0037

p10=0,0042

p11=0,0048

p12=0,0055

p13=0,0064

p14=0,0076

p15=0,0091

p16=0,0111

p17=0,0139

p18=0,0179

p19=0,0238

p20=0,0333

p21=0,0500

p22=0,0833

p23=0,1667

p24=0,5000

рi = 1

Определение количества информации на символ сообщения, составленного из данного алфавита.

Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:

Hmax = log2 24 = ln 24/ln 2 = 4,5850 бит/символ

Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:

H = – (0,0417*log20,0417 + 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022 + 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029 + 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042 + 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064 + 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111 + 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238 + 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833 + 0,1667*log20,1667 + 0,5000*log20,5000) =

= 2,6409 бит/символ

Недогруженность символов в данном случае:

N = Нmax – Н = 4,5850 – 2,6409 = 1,9441 бит/символ

Вычисление скорости передачи информации.

С= – (0,0417*log20,0417 + 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022 + 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029 + 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042 + 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064 + 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111 + 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238 + 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833 + 0,1667*log20,1667 + 0,5000*log20,5000) /

(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек

Избыточность сообщений, составленных из данного алфавита.

D = 1 – (Н/Нmax) = 1 – (2,6409 / 4,5850) = 0,4240

Построение оптимального кода

1

p24=0,5000

0,5

0

0

2

p23=0,1667

0,5

1

0,25

1

0,1666

1

111

3

p22=0,0833

1

1

0,0833

0

110

4

p21=0,0500

1

0,25

0

0

0,05

1 0

1000

5

p1=0,0417

1

0

0

0,0690

1

0,0357

1

10011

6

p20=0,0333

1

0

0,1190

0

1

0,0333

0

10010

7

p19=0,0238

1

0

1

1

0,0428

1

0,0178

1

101111

8

p18=0,0179

1

0

1

1

1

0,025

0

0,0138

0

1011100

9

p17=0,0139

1

0

1

1

0

0,025

1

101101

10

p16=0,0111

1

0

1

0,0666

1

1

0

101110

11

p15=0,0091

1

0

1

0,0642

0

0

1

0,0090

1

1010011

12

p14=0,0076

1

0

1

0

0

1

0,0102

0

0,0054

0

10100100

13

p13=0,0064

1

0

1

0

0

0,0166

0

0,0064

1

1010001

14

p12=0,0055

1

0

1

0

0

0,0166

1

0,0064

1

1010011

15

p11=0,0048

1

0

1

0

0,0333

1

1

1

0,0047

1

10101111

16

p10=0,0042

1

0

1

0

1

1

0,0088

1

0

0,0032

0

101011100

17

p9=0,0037

1

0

1

0

1

1

0,0078

0

0,0036

1

10101101

18

p8=0,0033

1

0

1

0

1

1

0,0078

1

0,0036

0

10101110

19

p7=0,0029

1

0

1

0

1

0

1

0

10101010

20

p6=0,0026

1

0

1

0

1

0,0167

0

1

0,0026

1

0,0026

1

101010111

21

p5=0,0024

1

0

1

0

1

0,0147

0

1

1

0,0024

0

101010110

22

p4=0,0022

1

0

1

0

1

0

0

0,0022

0

10101000

23

p3=0,0020

1

0

1

0

1

0

0

0,0038

1

0,0020

1

101010011

24

p2=0,0018

1

0

1

0

1

0

0,0083

0

1

0,0018

0

101010010


Буква

Вероятность появления буквы

Кодовые слова

Число знаков в кодовом слове

Pi· li

A[1] (p24)

0,5000

0

1

0,5

A[2] (p23)

0,1667

111

3

0,50001

A[3] (p22)

0,0833

110

3

0,2500

A[4] (p21)

0,0500

1000

4

0,2000

A[5] (p 1)

0,0417

10011

5

0,2083

A[6] (p20)

0,0333

10010

5

0,1667

A[7] (p19)

0,0238

101111

6

0,1429

A[8] (p18)

0,0179

1011100

7

0,1250

A[9] (p17)

0,0139

101101

6

0,0833

A[10] (p16)

0,0111

101110

6

0,0667

A[11] (p15)

0,0091

1010011

7

0,0636

A[12] (p14)

0,0076

10100100

8

0,0606

A[13] (p13)

0,0064

1010001

7

0,0449

A[14] (p12)

0,0055

1010011

7

0,0385

A[15] (p11)

0,0048

10101111

8

0,0381

A[16] (p10)

0,0042

101011100

9

0,0375

A[17] (p9)

0,0037

10101101

8

0,0294

A[18] (p8)

0,0033

10101110

8

0,0261

A[19] (p7)

0,0029

10101010

8

0,0234

A[20] (p6)

0,0026

101010111

9

0,0237

A[21] (p5)

0,0024

101010110

9

0,0214

A[22] (p4)

0,0022

10101000

8

0,0173

A[23] (p3)

0,0020

101010011

9

0,0178

A[24] (p2)

0,0018

101010010

9

0,0163

Определение количества информации на символ сообщения. Построение оптимального кода.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4121
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее