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

Порядок и основные этапы построения двоичных неравномерных эффективных кодов с помощью методики Хаффмена. Сравнительная характеристика полученных кодов. Кодирование текста построенными кодами. Разработка марковских процедур для кодирования слов.

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 29.09.2011
Размер файла 520,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

1111111111100001111111111101100111

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

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

111110100011111001100001

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

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

111001000111010100011

Длина двоичной последовательности: 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

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

11111111101110011111

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

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

111111110101011111111111111111111

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

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

111100010001010111111111

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

Размещено на Allbest.ru


Подобные документы

  • Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих многократные ошибки. Отличие методики построения кодов БЧХ от обычных циклических. Конкретные примеры процедуры кодирования, декодирования, обнаружения и исправления ошибок.

    реферат [158,2 K], добавлен 16.07.2009

  • Циклические коды как подкласс (подмножество) линейных кодов, пошаговый алгоритм и варианты их кодирования и декодирования. Методика построения интерфейса отладочного модуля. Элементарный план и элементы отладки декодирующего модуля циклических кодов.

    лабораторная работа [133,8 K], добавлен 06.07.2009

  • Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.

    курсовая работа [212,6 K], добавлен 25.02.2009

  • Разработка алгоритма и программы кодирования и декодирования данных кодом Рида-Малера. Понятие избыточных кодов, их применение. Корелляционный код. Особенности построения простых помехоустойчивых кодов Рида-Маллера. Рассмотрение частных случаев.

    курсовая работа [31,9 K], добавлен 09.03.2009

  • История применения кодов. Технология применения кодов в современных условиях. Анализ "экстремальных кодов" - кодов, границы параметров которых достигают равенства. Способность кода корректировать ошибки, ее зависимость от величины кодового расстояния.

    контрольная работа [164,9 K], добавлен 14.07.2012

  • Оптимальное статистическое (экономное) кодирование. Основные понятия и определения теории кодирования. Принципы построения оптимальных кодов. Способность системы осуществлять прием информации в условиях наличия помех. Увеличение мощности сигналов.

    реферат [69,3 K], добавлен 09.07.2009

  • Помехоустойчивое кодирование, правильность передачи информации. Устранение ошибок в симплексных каналах связи с помощью корректирующих кодов. Способы обнаружения ошибок - контрольное суммирование, проверка на нечетность. Применение циклических кодов.

    реферат [28,1 K], добавлен 03.08.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.