Эффективные коды

  • Вид работы:
    Практическое задание
  • Предмет:
    Информационное обеспечение, программирование
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    79,16 kb
  • Опубликовано:
    2011-09-29
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Эффективные коды

1.      Построим двоичные неравномерные эффективные коды

Для получения кодов для кодирования по одному символу используем методику Хаффмена:

Р(А) = 0,811

Р(В) = 0,040

Р(D) = 0,149


Слово

Вероятность

КК

Длина КК

А

0,811

1

1

В

0,040

01

2

D

0,149

00

2


Для получения кодов для кодирования по два символа используем методику Хаффмена, предварительно рассчитав частоты появления слов, которые состоят из двух символов:

Р(АА) = Р(А)*Р(А) = 0,811*0,811 = 0,6577

Р(АВ) = Р(А)*Р(В) = 0,811*0,040 = 0,0324

Р(АD) = Р(А)*Р(D) = 0,811*0,149 = 0,1208

Р(BА) = Р(B)*Р(А) = 0,040*0,811 = 0,0324

Р(BB) = Р(B)*Р(B) = 0,040*0,040 = 0,0016

Р(BD) = Р(B)*Р(D) = 0,040*0,149 = 0,0060

Р(DА) = Р(D)*Р(А) = 0,149*0,811 = 0,1208

Р(DB) = Р(D)*Р(B) = 0,149*0,040 = 0,0060

Р(DD) = Р(D)*Р(D) = 0,149*0,149 = 0,0222


Слово

Вероятность

КК

Длина КК

АА

0,6577

1

1

АВ

0,0324

00111

5

АD

0,1208

01

2

ВА

0,0324

00110

5

ВВ

0,0016

0010111

7

ВD

0,0060

0010110

7

DA

0,1208

000

3

DB

0,0060

001010

6

DD

0,0222

00100

5


Для получения кодов для кодирования по три символа используем методику Хаффмена, предварительно рассчитав частоты появления слов, которые состоят из трех символов:

Р(ААА) = Р(А)*Р(А)*Р(А) = 0,811*0,811*0,811 = 0,5334

Р(ААВ) = Р(А)*Р(А)*Р(B) = 0,811*0,811*0,040 = 0,0263

Р(ААD) = Р(А)*Р(А)*Р(D) = 0,811*0,811*0,149 = 0,0980

Р(АBА) = Р(А)*Р(B)*Р(А) = 0,811*0,040*0,811 = 0,0263

Р(АBB) = Р(А)*Р(B)*Р(B) = 0,811*0,040*0,040 = 0,0013

Р(АBD) = Р(А)*Р(B)*Р(D) = 0,811*0,040*0,149 = 0,0048

Р(АDА) = Р(А)*Р(D)*Р(А) = 0,811*0,149*0,811 = 0,0980

Р(АDB) = Р(А)*Р(D)*Р(B) = 0,811*0,149*0,004 = 0,0048

Р(АDD) = Р(А)*Р(D)*Р(D) = 0,811*0,149*0,149 = 0,0180

Р(BАА) = Р(B)*Р(А)*Р(А) = 0,040*0,811*0,811 = 0,0263

Р(BАВ) = Р(B)*Р(А)*Р(B) = 0, 040*0,811*0,040 = 0,0013

Р(BАD) = Р(B)*Р(А)*Р(D) = 0, 040*0,811*0,149 = 0,0048

Р(BBА) = Р(B)*Р(B)*Р(А) = 0, 040*0,040*0,811 = 0,0013

Р(BBB) = Р(B)*Р(B)*Р(B) = 0, 040*0,040*0,040 = 0,0001

Р(BBD) = Р(B)*Р(B)*Р(D) = 0, 040*0,040*0,149 = 0,0002

Р(BDА) = Р(B)*Р(D)*Р(А) = 0, 040*0,149*0,811 = 0,0048

Р(BDB) = Р(B)*Р(D)*Р(B) = 0, 040*0,149*0,004 = 0,0002

Р(BDD) = Р(B)*Р(D)*Р(D) = 0, 040*0,149*0,149 = 0,0009

Р(DАА) = Р(D)*Р(А)*Р(А) = 0,149*0,811*0,811 = 0,0980

Р(DАВ) = Р(D)*Р(А)*Р(B) = 0, 149*0,811*0,040 = 0,0048

Р(DАD) = Р(D)*Р(А)*Р(D) = 0, 149*0,811*0,149 = 0,0180

Р(DBА) = Р(D)*Р(B)*Р(А) = 0, 149*0,040*0,811 = 0,0048

Р(DBB) = Р(D)*Р(B)*Р(B) = 0, 149*0,040*0,040 = 0,0002

Р(DBD) = Р(D)*Р(B)*Р(D) = 0, 149*0,040*0,149 = 0,0009

Р(DDА) = Р(D)*Р(D)*Р(А) = 0, 149*0,149*0,811 = 0,0180

Р(DDB) = Р(D)*Р(D)*Р(B) = 0, 149*0,149*0,004 = 0,0009

Р(DDD) = Р(D)*Р(D)*Р(D) = 0, 149*0,149*0,149 = 0,0033


Слово

Вероятность

КК

Длина КК

ААA

0,5334

1

1

АAВ

0,0263

010111

6

АAD

0,0980

001

3

AВА

0,0263

010110

6

AВВ

0,0013

0100011011

10

AВD

0,0048

01010011

8

ADA

0,0980

011

3

ADB

0,0048

01010010

8

ADD

0,0180

00011

5

ВАA

0,0263

010101

6

ВAВ

0,0013

0100011010

10

ВAD

0,0048

01010001

8

ВВА

0,0013

0101000011

10

ВВВ

0,0001

0101000010111

13

ВВD

0,0002

0101000010110

13

ВDA

0,0048

01000111

8

ВDB

0,0002

0101000010101

13

ВDD

0,0009

01010000100

11

DАA

0,0980

000

3

DAВ

0,0048

01000101

8

DAD

0,0180

010010

6

DВА

0,0048

01000100

8

DВВ

0,0002

0101000010100

13

DВD

0,0009

0101000001

10

DDA

0,0180

010000

6

DDB

0,0009

010100000

9

DDD

0,0033

010001100

9


2.      Сравним между собой построенные коды и их эффективность

Рассчитаем среднюю длину кодовой комбинации в расчете на один символ источника.

l ср (1) = 0,811*1 + 0,040*2 + 0,149*2 = 1,189

l ср (2) = [0,6577*1 + (0,0324 + 0,0324 + 0,0060 + 0,0222)*5 + (0,0016 + 0,0060)*7 + 0,128*3]/2 = 0,8929

l ср (3) = 2,5296/3 = 0,8432

Найдем относительную разницу между средней длиной кодовой комбинации и энтропией источника.

Н(х) = 0,8126

Видим, что наиболее эффективным будет код при кодировании по три символа.

3.      Построенными кодами закодируем фрагмент текста

AAAAAAAAAAADDAAAAAAAAAAABADAAA

Для кодирования по одному символу:

Длина двоичной последовательности: L = 34.

Для кодирования по два символа:

Длина двоичной последовательности: L = 24.

Для кодирования по три символа:

Длина двоичной последовательности: L = 21.

Для источника с памятью

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

Р(А) = 0,604

Р(В) = 0,175

Р(D) = 0,220


Р(АА) = Р(А)*Р (А/A) = 0,604*0,809 = 0,4886

Р(АВ) = Р(А)*Р (В/A) = 0,604*0,039 = 0,0236

Р(АD) = Р(А)*Р (D/A) = 0,604*0,152 = 0,0918

Р(BА) = Р(B)*Р (А/B) = 0,175*0,375 = 0,0656

Р(BB) = Р(B)*Р (B/B) = 0,175*0,534 = 0,0935

Р(BD) = Р(B)*Р (D/B) = 0,175*0,091 = 0,0159

Р(DА) = Р(D)*Р (А/D) = 0,220*0,226 = 0,0497

Р(DB) = Р(D)*Р (B/D) = 0,220*0,262 = 0,0576

Р(DD) = Р(D)*Р (D/D) = 0,220*0,512 = 0,1126

Неравномерные двоичные эффективные коды построим по методике Хаффмена.


Слово

Вероятность

КК

Длина КК

АА

0,4886

1

1

АВ

0,0236

011011

6

АD

0,0918

0111

4

ВА

0,0656

0101

4

ВВ

0,0935

001

3

ВD

0,0159

011010

6

DA

0,0497

01100

5

DB

0,0576

0100

4

DD

0,1126

000

3


2.      Разработаем марковские процедуры для кодирования слов по одному символу:

Для состояния А:

Р (А/А) = 0,809

Р (В/А) = 0,039

Р (D/А) = 0,152


Символ, что ожидается

Условная вероятность

КК

Длина КК

А

0,809

1

1

В

0,039

01

2

D

0,152

00

2


Для состояния В:

Р (А/В) = 0,375

Р (В/В) = 0,534

Р (D/В) = 0,091


Символ, что ожидаетсяУсловная вероятностьККДлина КК




А

0,375

11

2

В

0,534

0

1

D

0,091

10

2


Для состояния D:

Р (А/D) = 0,226

Р (В/D) = 0,262

Р (D/D) = 0,512


Символ, что ожидаетсяУсловная вероятностьККДлина КК




А

0,226

11

2

В

0,262

10

2

D

0,512

0

1


Разработаем марковские процедуры для кодирования слов по два символа:

двоичный неравномерный код марковский

Р (АА/А) = Р (А/A)*Р (А/A) = 0,809*0,809 = 0,6545

Р (АВ/А) = Р (А/A)*Р (В/A) = 0,809*0,039 = 0,0316

Р (АD/А) = Р (А/A)*Р (D/A) = 0,809*0,152 = 0,1230

Р (BА/А) = Р (B/A)*Р (А/B) = 0,039*0,375 = 0,0146

Р (BB/А) = Р (B/A)*Р (B/B) = 0,039*0,534 = 0,0208

Р (BD/А) = Р (B/A)*Р (D/B) = 0,039*0,091 = 0,0035

Р (DА/А) = Р (D/A)*Р (А/D) = 0,152*0,226 = 0,0343

Р (DB/А) = Р (D/A)*Р (B/D) = 0,152*0,262 = 0,0398

Р (DD/А) = Р (D/A)*Р (D/D) = 0,152*0,512 = 0,0778


Слово

Вероятность

КК

Длина КК

АА

0,6545

1

1

АВ

0,0316

0111

4

АD

0,1230

001

3

ВА

0,0146

000111

6

ВВ

0,0208

00010

5

ВD

0,0035

000110

6

DA

0,0343

0110

4

DB

0,0398

0000

4

DD

0,0778

010

3


Для состояния B:

Р (АА/B) = Р (А/B)*Р (А/A) = 0,375*0,809 = 0,3034

Р (АВ/B) = Р (А/B)*Р (В/A) = 0,375*0,039 = 0,0146

Р (АD/B) = Р (А/B)*Р (D/A) = 0,375*0,152 = 0,0570

Р (BА/B) = Р (B/B)*Р (А/B) = 0,534*0,375 = 0,2003

Р (BB/B) = Р (B/B)*Р (B/B) = 0,534*0,534 = 0,2852

Р (BD/B) = Р (B/B)*Р (D/B) = 0,534*0,091 = 0,0486

Р (DА/B) = Р (D/B)*Р (А/D) = 0,091*0,226 = 0,0206

Р (DB/B) = Р (D/B)*Р (B/D) = 0,091*0,262 = 0,0238

Р (DD/B) = Р (D/B)*Р (D/D) = 0,091*0,512 = 0,0466


СловоВероятностьККДлина КК




АА

0,3034

11

2

АВ

0,0146

001011

6

АD

0,0570

0011

4

ВА

0,2003

01

2

ВВ

0,2852

10

2

ВD

0,0486

0001

4

DA

0,0206

001010

6

DB

0,0238

00100

5

DD

0,0466

0000

4


Для состояния D:

Р (АА/D) = Р (А/D)*Р (А/A) = 0,226*0,809 = 0,1828

Р (АВ/D) = Р (А/D)*Р (В/A) = 0,226*0,039 = 0,0088

Р (АD/D) = Р (А/D)*Р (D/A) = 0,226*0,152 = 0,0344

Р (BА/D) = Р (B/D)*Р (А/B) = 0,262*0,375 = 0,0983

Р (BB/D) = Р (B/D)*Р (B/B) = 0,262*0,534 = 0,1399

Р (BD/D) = Р (B/D)*Р (D/B) = 0,262*0,091 = 0,0238

Р (DА/D) = Р (D/D)*Р (А/D) = 0,512*0,226 = 0,1157

Р (DB/D) = Р (D/D)*Р (B/D) = 0,512*0,262 = 0,1341

Р (DD/D) = Р (D/D)*Р (D/D) = 0,512*0,512 = 0,2621


СловоВероятностьККДлина КК




АА

0,1828

11

2

АВ

0,0088

011111

6

АD

0,0344

01110

5

ВА

0,0983

0110

4

ВВ

0,1399

010

3

ВD

0,0238

011110

6

DA

0,1157

101

3

DB

0,1341

100

3

DD

0,2621

00

2


3.      Сравним между собой разработанные коды и оценим их эффективность.

Для кодирования по одному символу:


Для кодирования по два символа:


4.      Разработанными кодами и процедурами закодируем фрагмент текста:

АААААААААААААААААААDBBAAAAAAAA

При кодировании кодами по два символа:

Длина кодовой комбинации: L = 20
Кодирование процедурами будем выполнять в порядке справа налево, считая, что перед появлением первого символа на выходе источника был символ А.

При кодировании процедурами по одному символу:

Длина кодовой комбинации: L = 33

При кодировании процедурами по два символа:

Длина кодовой комбинации: L = 24

Похожие работы на - Эффективные коды

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!