Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2009
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН-33
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НУ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра САПР
ЗВІТ
про виконання лабораторної роботи № 2
на тему:
“МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ”
З курсу “ Методи та засоби комп’ютерних інформаційних технологій”
Львів 2009
МЕТА РОБОТИ
Мета роботи – отримати практичні навики використання методів оптимального кодування.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Різновидності кодів.
По формі представлення в каналі передачі розрізняють послідовні і паралельні коди. При послідовних кодах елементарні сигнали, що передають кодову комбінацію посилаються в канал передачі послідовно в часі. Вони можуть бути розділені часовим інтервалом або опитуватися в певні моменти часу (наприклад, як у послідовному інтерфейсі RS - 232 C).
Для паралельних кодів потрібні багатопровідні канали, тому при передачі інфрмації на значну відстань вони використовуються рідко через великі затрати (наприклад, паралельний інтерфейс Centronics). Паралельне представлення найчастіше використовується коли потрібна висока швидкість передачі даних (Centronics – 80 – 120 Кбайт/сек, сучасні двонаправлені системи – до 250 Кбайт/сек).
По можливості виявлення та виправлення помилок розрізняють прості (примітивні) і коректуючі коди.
В простих кодах помилка у будь-якому елементі кодової комбінації приводить до неправильного прийому декодованого повідомлення.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
Комбінаторні коди будуються по законах теорії поєднань. Наприклад, код з m різних символів утворює кодові комбінації з n<m символів. Довжина коду постійна і рівна n, а можлива кількість кодових комбінацій
;
Наприклад, комбінації з 3 по 2: a, b, c =>ab, ac, bc.
АРИФМЕТИЧНІ (ЧИСЛОВІ, ЦИФРОВІ) КОДИ БАЗУЮТЬСЯ НА СИСТЕМАХ ЧИСЛЕННЯ І НАЙЧАСТІШЕ ВИКОРИСТОВУЮТЬСЯ В ТЕХНІЧНИХ СИСТЕМАХ.
Рівномірні прості цифрові коди.
СИСТЕМИ ЧИСЛЕННЯ, НА ОСНОВІ ЯКИХ БУДУЮТЬСЯ ЦИФРОВІ КОДИ, ПОДІЛЯЮТЬСЯ НА ПОЗИЦІЙНІ І НЕПОЗИЦІЙНІ.
В позиційних сисмтемах значення символа залежить від його позиції в ряду символів, що утворюють число. В непозиційних – ні. В позиційних системах значення кожного наступного розряду більше від попереднього в m раз (m – основа системи чиселення).
При цьому будь-яке n-розрядне число може бути представлене у вигляді суми
де: lі - значення і-го розрядного коефіцієнта.
Кількість можливих значень lі рівна m (від 0 до m-1).
Приклад: чотирьохрозрядне десяткове число 4752=4*103+7*102+5*101+2*100.
Максимальна кількість кодових комбінацій Nmax=mn.
На практиці в технічних системах найчастіше використовуються двійкові коди
де: li = 0(1; Nmax = 2n;
N=2010=0*25+1*24+0*23+1*22+0*21+0*20 (0101002)
Двійковий код зручний для обробки машиною, однак для оператора громіздкий, тому використовують вісімкову або шістнадцяткову системи з основою рівною 23 і 2 4 відповідно.
N=(0248)= (0000101002)
N=(01416)= (0000000101002)
Для запису шістнадцяткових чисел використовуються цифри 0-9 та букви А-F.
Складні коди.
Складні коди базуються на системах числення, що мають дві і більше основ. При такому кодуванні числа, задані в системі з основою q, записуються за допомогою цифр іншої системи числення з основою p<q.
Найбільш характерні двійково-десяткові коди. Вони використовуються як проміжні при переводі десяткових у двійкові та навпаки.
У двійково-десятковій системі числення основна система числення десяткова. Однак кожна цифра десяткового числа записується у вигляді чотирьохрозрядного двійкового числа.
Найбільш часто використовують чотирьохрозрядні двійкові вагові коди 8-4-2-1; 7-4-2-1; 5-1-2-1; 2-4-2-1. Так як з 16 комбінацій використовують 10, то код – надлишковий.
Приклад:
8 4 2 1 7 4 2 1 5 1 2 1 2 4 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
2 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
4 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0
5 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1
6 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0
7 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1
8 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0
9 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1
Рефлексні (відбиті) коди.
У простому (двійковому) коді при переході від одного числа до сусіднього може бути зміна цифр у кількох розрядах. Це може спричинити значні помилки при кодуванні неперервних повідомлень. Так, наприклад, кодування секторним перетворювачем кута при переході від 7 до 8 (1112 => 10002) тимчасово може дати значення 1111 (помилка у 2 рази).
Для усунення цього явища використовують спеціальні двійкові коди, у яких при переході від числа до числа міняється тільки один розряд. При цьому похибка за рахунок неоднозначності зчитування не буде перевищувати одиниці цього числа.
Одним з таких кодів є код Грея. Це непозиційний код, вага одиниці якого не визначається номером розряду. У цих кодах спостерігається симетричність відносно деякої осі відбиття – тобто ідентичність молодших розрядів. Звідси - “рефлексний код” (reflect – відбивати). У коді Грея вага одиниці у j-му розряді по абсолютній величині визначається формулою
Wj=
Причому знак сумованих членів додатній для всіх непарних одиниць в числі (записаних у коді Грея зліва направо) і від’ємний для всіх парних
[1101101]г=--++=64+32+16+8+4+2+1-32-16-8-4-2-1-8-4-2-1+4+2+1+1=57
двійковий код код Грея двійковий код код Грея
0 0000 0000 8 1000 1100
1 0001 0001 9 1001 1101
2 0010 0011 10 1010 1111
3 0011 0010 11 1011 1110
4 0100 0110 12 1100 1010
5 0101 0111 13 1101 1011
6 0110 0101 14 1110 1001
7 0111 0100 15 1111 1000
Оптимальне (ефективне) кодування.
Ентропія джерела повідомлень визначається формулою
де: - ймовірність появи xi з N символів алфавіту джерела. N – об’єм алфавіту джерела.
Теорема Шенона для каналу без завад: в каналі зв’язку без завад можна так перетворити послідовність символів джерела, що середня довжина символів коду буде як завгодно близька до ентропії джерела повідомлень.
Ентропія H(x) виступає кількісною мірою різноманітності повідомлень джерела і є його основною характеристикою. Ентропія джерела максимальна, якщо ймовірності повідомлень є рівними. Якщо одне повідомлення достовірне, а інші неможливі, то H(x)=0. Одиниця виміру ентропії – 1 біт. Це та невизначеність, коли джерело має однакову ймовірність двох можливих повідомлень (0 або 1).
Ентропія H(x) визначає середню кількість двійкових знаків, необхідних для кодування початкових символів джерела. Наприклад, для російських букв n=32=25. Якщо вони подаються рівномірно і незалежні між собою, то H(x)<5. Для російського літературного тексту H(x)=1.5 біт, для віршів H(x)=1 біт, а для телеграм H(x)=0.8 біт. Це означає, що при певному способі кодування на передачу букви може бути затрачено відповідно 1.5, 1, 0.8 двійкових символів.
Якщо символи нерівноімовірні і залежні, то ентропія буде менша від свого максимального значення Нmax(x)=log2N. При цьому можливе деяке більш економне (ефективне) кодування, при якому на кожен символ буде в середньому затрачено n*=H(x) символів коду. Коефіцієнт надлишковості визначається такою формулою
Кнадл=1-H(x)/Hmax(x)
Для характеристики досягнутого стиснення використовують коефіцієнт стиснення
Кстисн=Lпочат/Lстисн
Можна показати, що Кнадл>Кстисн.
Різні методи оптимального кодування базуються на зменшенні надлишковості викликаної неоднаковою апріорною ймовірностю символів або залежністю між порядком надходження символів.
В першому випадку для кодування використовується нерівномірний код - більш ймовірні символи мають коротший код, а менш ймовірні – довший.
В другому випадку переходять від кодування окремих символів до кодування їх груп. При цьому здійснюється укрупнення алфавіту джерела, через те N зростає. Загальна надлишковість укрупненого алфавіту при цьому не міняється. Однак, зменшення надлишковості обумовлене зменшенням різниці ймовірностей різних груп символів. Таким чином, процес кодування зводиться до двох операцій: укрупнення алфавіту і кодування оптимальним нерівномірним кодом.
Стиснення буває із втратами і без втрат. Втрати допустимі при стисненні аудіо-та відеоінформації (наприклад, MPEG - 20 до 1; MPEG3 - 100 до 1; TIFF - 10до 1 при 10% втрат, 100 до 1 при 20% втрат і т.д.).
Метод Шенона-Фано
В цьому методі для кожного символа формується бітовий код, довжина якого залежить від частоти появи символа. Чим менша частота, тим довший код. Визначення частоти (ймовірності) символа буває статичне (на основі таблиці даних) та динамічне (коли відомості про ймовірність появи символів визначаються на основі обробки потоку даних). Статичний варіант використовується в архіваторах ARK, PKZIP.
Кодування здійснюється таким чином (рис. 1):
Всі символи записуються в таблицю по зменшенню їх частоти. Потім вони поділяються на дві групи так, щоб суми частот для отриманих груп були максимально близькі. Для першої групи перший біт коду встановлюється рівним 1, а для другої – 0.
Потім групи знову поділяємо на дві і визначаємо наступні розряди коду. Процес продовжується поки в групі не залишиться тільки один символ.
Номер Символ Частота Код
1 a 10 11
2 b 8 10
----------------------------- ----------------------------
3 c 6 011
4 d 5 010
5 e 4 001
6 f 3 000
Рис. 1.
Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) будуть отримані різні коди для символів (рис. 2).
Символ Частота Код Символ Частота Код
с 22 11 с 22 11
e 20 101 e 20 10
h 16 100 --------------------------------------------
----------------------------------------------- h 16 011
i 16 011 і 16 010
a 10 010 a 10 001
k 10 001 k 10 0001
m 4 0001 m 4 00001
b 2 0000 b 2 00000
Рис. 2.
Можливий варіант програмної реалізації методу базується на формуванні і обробці такої таблиці
Nгр
Np
Nk
S
Код
1
1
2
18
1
3
6
18
0
2
1
1
10
11
2
2
8
10
3
3
4
11
01
5
6
7
00
4
3
3
6
011
4
4
5
010
5
5
5
4
001
6
6
3
000
Ця таблиця забезпечує зручний запис алгоритму поділу на підгрупи і формування кодів. Перша група (Nгр=1) складається з двох підгруп: перша - починається з першого символа (Np=1) і закінчується другим (Nк=2), друга – починається з третього символа (Nр=3) і закінчується шостим (Nк=6). Сума частот першої підгрупи S=18, другої S=18. Друга група (Nгр=2) формується в результаті поділу першої підгрупи з першої групи і складається теж з двох підгруп: перша – починається з першого символа (Nр=1) і ним закінчується (Nк=1), друга – починається другим символом (Nр=2) і ним закінчується (Nк=2). Третя група описує процес поділу другої підгрупи з першої групи. Процуес продовжується до тих пір поки кожна підгрупа не буде складатися тільки з одного символа (Nр=Nк). Відповідний новий біт коду кожної групи визначається таким чином: для першої підгрупи він встановлюється рівним одиниці, а для другої підгрупи – нулю.
Метод Хафмана.
Метод полягає в побудові кодового дерева Хафмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках:
Всім символам ставиться у відповідність одна з вершин дерева.
Об’єднуємо дві вершини з мінімальними частотами і для нової вершини вказуємо сумарну частоту.
Переходимо на пункт 2, доки не об’єднаємо всі вершини.
Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0 (рис.3).
Для програмної реалізації методу можна використати таку таблицю
c22 22 22 26 32 42 58 100 01
e20 20 20 22 26 32 42 00
h16 16 16 20 22 26 111
l16 16 16 16 20 110
a10 10 16 16 100
k10 10 10 1011
m46 10101
b2 10110
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Варіант
5
Частота a
30
Частота b
20
Частота c
10
Частота d
5
Частота e
5
Частота f
4
Частота g
3
Код програми, Метод Шенона-Фано
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
struct _value
{
char name;
int freq;
char code[8];
}*value;
struct _list
{
_list *next;
char name;
int freq;
}*startList=0;
int N=0;
void count(char val)
{
if(startList)
{
int flag=1;
_list *cur=startList;
for(;;)
{
if(cur->name==val)
{
cur->freq++;
flag=0;
}
if(cur->next)cur=cur->next;
else break;
}
if(flag)
{
cur->next=(_list*)malloc(sizeof(_list));
cur->next->next=0;
cur=cur->next;
cur->name=val;
cur->freq=1;
N++;
}
}
else
{
startList=(_list*)malloc(sizeof(_list));
startList->next=0;
startList->name=val;
startList->freq=1;
N++;
}
}
void sortList()
{
_list tmp;
for(int i=0;i<N;i++)
for(_list *cur=startList;cur->next;cur=cur->next)
if(cur->freq<cur->next->freq)
{
tmp.freq = cur->freq;
tmp.name = cur->name;
cur->freq = cur->next->freq;
cur->name = cur->next->name;
cur->next->freq = tmp.freq;
cur->next->name = tmp.name;
}
}
void toarray()
{
for(int i=0;i<N;i++)
{
for(int j=0;j<8;j++)value[i].code[j]=0;
value[i].freq=startList->freq;
value[i].name=startList->name;
startList=startList->next;
}
}
void getcode(int start,int end,int pos)
{
struct
{
int val;
int pos;
}min;
if(start!=end)
{
int E1=0,E2=0,diff;
for(int i=start;i<=end;i++)E1+=value[i].freq;
for(i=start,min.val=E1;i<=end;i++)
{
E1-=value[i].freq;
E2+=value[i].freq;
diff=abs(E1-E2);
if(min.val>diff)
{
min.val=diff;
min.pos=i;
}
}
for(i=start;i<=min.pos;i++)value[i].code[pos]='1';
for(;i<=end;i++)value[i].code[pos]='0';
getcode(start,min.pos,pos+1);
getcode(min.pos+1,end,pos+1);
}
}
int main(int argc, char* argv[])
{
if(argc<2)
{
argv[1] = (char*)malloc(256*sizeof(char));
argv[2] = (char*)malloc(256*sizeof(char));
printf("ERROR No file!\nPlease enter input filename:\n");
scanf("%s",argv[1]);
printf("Please enter output filename:\n");
scanf("%s",argv[2]);
}
FILE *f1=fopen(argv[1],"r");
FILE *f2=fopen(argv[2],"w");
value = (_value*)malloc(N*sizeof(value));
for(int i=0;!feof(f1);i++)
{
char c;
fscanf(f1,"%c",&c);
count(c);
}
sortList();
toarray();
getcode(0,N-1,0);
fprintf(f2,"%d\n",N);
for(i=0;i<N;i++)fprintf(f2,"%c\t%d\t%s\n",value[i].name,value[i].freq,value[i].code);
fclose(f1);
fclose(f2);
return 0;
}
Вхідний файл:
Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccdddddeeeeeffffggg
Вихідний файл:
7
a 30 1
b 20 01
c 10 0011
d 5 0010
f 5 0001
e 4 00001
g 4 00000
Код програми, Метод Хафмана.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
struct _value
{
char name;
int freq;
char code[8];
}*value;
struct _list
{
_list *next;
_list *prev;
_list *left;
_list *right;
char name;
int freq;
}*startList=0;
int N=0;
void count(char val)
{
if(startList)
{
int flag=1;
_list *cur=startList;
for(;;)
{
if(cur->name==val)
{
cur->freq++;
flag=0;
}
if(cur->next)cur=cur->next;
else break;
}
if(flag)
{
cur->next=(_list*)malloc(sizeof(_list));
cur->next->next=0;
cur->next->prev=cur;
cur=cur->next;
cur->name=val;
cur->freq=1;
cur->left=0;
cur->right=0;
N++;
}
}
else
{
startList=(_list*)malloc(sizeof(_list));
startList->next=0;
startList->prev=0;
startList->name=val;
startList->freq=1;
startList->left=0;
startList->right=0;
N++;
}
}
void sortList()
{
_list tmp;
for(int i=0;i<N;i++)
for(_list *cur=startList;cur->next;cur=cur->next)
if(cur->freq<cur->next->freq)
{
tmp.freq = cur->freq;
tmp.name = cur->name;
cur->freq = cur->next->freq;
cur->name = cur->next->name;
cur->next->freq = tmp.freq;
cur->next->name = tmp.name;
}
}
void sortArr()
{
_value tmp;
for(int i=0;i<N;i++)
for(int j=0;j<N-1;j++)
if(value[j].name>value[j+1].name)
{
tmp = value[j];
value[j]=value[j+1];
value[j+1]=tmp;
}
}
void maketree()
{
_list *min1,*min2,*tmp;
while(startList->next)
{
min2=startList;
for(_list *cur=startList;cur;cur=cur->next)if(cur->freq<min2->freq)min2=cur;
if(min2!=startList)min1=startList;
else min1=startList->next;
for(cur=startList;cur;cur=cur->next)
{
if(cur==min2)continue;
if(cur->freq<min1->freq)min1=cur;
}
if(min2->prev)min2->prev->next=min2->next;
if(min2->next)min2->next->prev=min2->prev;
tmp =(_list*)malloc(sizeof(_list));
tmp->name=0;
tmp->freq=min1->freq+min2->freq;
if(min1->prev!=min2)tmp->prev=min1->prev;
else tmp->prev=min1->prev->prev;
if(tmp->prev)tmp->prev->next=tmp;
else startList=tmp;
if(min1->next!=min2)tmp->next=min1->next;
else tmp->next=min1->next->next;
if(tmp->next)tmp->next->prev=tmp;
tmp->left=min1;
tmp->right=min2;
if(min2==startList)startList=startList->next;
min1->prev=0;
min1->next=0;
min2->prev=0;
min2->next=0;
}
}
int KK=0;
void getcode(_list *cur,const char c[8])
{
if(cur->name)
{
for(int j=0;j<8;j++)value[KK].code[j]=c[j];
value[KK].freq=cur->freq;
value[KK].name=cur->name;
KK++;
}
else
{
char c2[8];
for(int i=0;i<8;i++)c2[i]=c[i];
for(i=0;c2[i];i++);
if(cur->left)
{
c2[i]='1';
getcode(cur->left, c2);
}
if(cur->right)
{
c2[i]='0';
getcode(cur->right, c2);
}
}
}
int main(int argc, char* argv[])
{
if(argc<2)
{
argv[1] = (char*)malloc(256*sizeof(char));
argv[2] = (char*)malloc(256*sizeof(char));
printf("ERROR No file!\nPlease enter input filename:\n");
scanf("%s",argv[1]);
printf("Please enter output filename:\n");
scanf("%s",argv[2]);
}
FILE *f1=fopen(argv[1],"r");
FILE *f2=fopen(argv[2],"w");
value = (_value*)malloc(N*sizeof(value));
for(int i=0;!feof(f1);i++)
{
char c;
fscanf(f1,"%c",&c);
count(c);
}
sortList();
maketree();
char a[8]={0,0,0,0,0,0,0,0};
getcode(startList,a);
sortArr();
fprintf(f2,"%d\n",N);
for(i=0;i<N;i++)fprintf(f2,"%c\t%d\t%s\n",value[i].name,value[i].freq,value[i].code);
fclose(f1);
fclose(f2);
return 0;
}
Вхідний файл:
Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccdddddeeeeeffffggg
Вихідний файл:
7
a 30 10
b 20 01
c 10 111
d 5 001
e 5 000
f 4 1101
g 4 1100
ВИСНОВОК
На цій лабораторній роботі я отримав практичні навики використання методів оптимального кодування.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора