Эффективные коды
Порядок и основные этапы построения двоичных неравномерных эффективных кодов с помощью методики Хаффмена. Сравнительная характеристика полученных кодов. Кодирование текста построенными кодами. Разработка марковских процедур для кодирования слов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 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Изучение сущности циклических кодов - семейства помехоустойчивых кодов, включающих в себя одну из разновидностей кодов Хэмминга. Основные понятия и определения. Методы построения порождающей матрицы циклического кода. Понятие открытой системы. Модель OSI.
контрольная работа [99,5 K], добавлен 25.01.2011История классификации и кодирования. Стандартизация передачи записей в электронную историю болезни. Клинические коды Рида RCC. Системы медицинской классификации в Украине. Унифицированная система медицинского языка UMLS. Особенности и классификация кодов.
реферат [38,2 K], добавлен 13.12.2009Анализ методов сверточного кодирования. Понятие канала связи и корректирующих кодов, характеристика автомата типа Мура. Особенности сверточного декодирования Витерби. Сущность разработки программного обеспечения системы кодирования сверточным кодом.
дипломная работа [4,9 M], добавлен 11.03.2012
