Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2004
Тип роботи:
Лабораторна робота
Предмет:
Методи i засоби комп'ютерних інформаційних технологій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра САПР
Звіт
до лабораторної роботи №2
на тему:
МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ
Виконав:
студент групи КН – 3
Львів 2004
МЕТА РОБОТИ
Мета роботи – отримати практичні навики використання методів оптимального кодування.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Різновидності кодів.
По формі представлення в каналі передачі розрізняють послідовні і паралельні коди. При послідовних кодах елементарні сигнали, що передають кодову комбінацію посилаються в канал передачі послідовно в часі. Вони можуть бути розділені часовим інтервалом або опитуватися в певні моменти часу (наприклад, як у послідовному інтерфейсі RS - 232 C).
Для паралельних кодів потрібні багатопровідні канали, тому при передачі інфрмації на значну відстань вони використовуються рідко через великі затрати (наприклад, паралельний інтерфейс Centronics). Паралельне представлення найчастіше використовується коли потрібна висока швидкість передачі даних (Centronics – 80 – 120 Кбайт/сек, сучасні двонаправлені системи – до 250 Кбайт/сек).
По можливості виявлення та виправлення помилок розрізняють прості (примітивні) і коректуючі коди.
В простих кодах помилка у будь-якому елементі кодової комбінації приводить до неправильного прийому декодованого повідомлення.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
Комбінаторні коди будуються по законах теорії поєднань. Наприклад, код з m різних символів утворює кодові комбінації з n<m символів. Довжина коду постійна і рівна n, а можлива кількість кодових комбінацій
EMBED Equation.3 ;
Наприклад, комбінації з 3 по 2: a, b, c =>ab, ac, bc.
Арифметичні (числові, цифрові) коди базуються на системах числення і найчастіше використовуються в технічних системах.
2.1.Рівномірні прості цифрові коди.
Системи числення, на основі яких будуються цифрові коди, поділяються на позиційні і непозиційні.
В позиційних сисмтемах значення символа залежить від його позиції в ряду символів, що утворюють число. В непозиційних – ні. В позиційних системах значення кожного наступного розряду більше від попереднього в m раз (m – основа системи чиселення).
При цьому будь-яке n-розрядне число може бути представлене у вигляді суми
EMBED Equation.3
де: lі - значення і-го розрядного коефіцієнта.
Кількість можливих значень lі рівна m (від 0 до m-1).
Приклад: чотирьохрозрядне десяткове число 4752=4*103+7*102+5*101+2*100.
Максимальна кількість кодових комбінацій Nmax=mn.
На практиці в технічних системах найчастіше використовуються двійкові коди
EMBED Equation.3
де: li = 01; Nmax = 2n;
N=2010=0*25+1*24+0*23+1*22+0*21+0*20 (0101002)
Двійковий код зручний для обробки машиною, однак для оператора громіздкий, тому використовують вісімкову або шістнадцяткову системи з основою рівною 23 і 2 4 відповідно.
EMBED Equation.3
N=(0248)= (0000101002)
EMBED Equation.3
N=(01416)= (0000000101002)
Для запису шістнадцяткових чисел використовуються цифри 0-9 та букви А-F.
Складні коди.
Складні коди базуються на системах числення, що мають дві і більше основ. При такому кодуванні числа, задані в системі з основою q, записуються за допомогою цифр іншої системи числення з основою p<q.
Найбільш характерні двійково-десяткові коди. Вони використовуються як проміжні при переводі десяткових у двійкові та навпаки.
У двійково-десятковій системі числення основна система числення десяткова. Однак кожна цифра десяткового числа записується у вигляді чотирьохрозрядного двійкового числа.
Рефлексні (відбиті) коди.
У простому (двійковому) коді при переході від одного числа до сусіднього може бути зміна цифр у кількох розрядах. Це може спричинити значні помилки при кодуванні неперервних повідомлень. Так, наприклад, кодування секторним перетворювачем кута при переході від 7 до 8 (1112 => 10002) тимчасово може дати значення 1111 (помилка у 2 рази).
Для усунення цього явища використовують спеціальні двійкові коди, у яких при переході від числа до числа міняється тільки один розряд. При цьому похибка за рахунок неоднозначності зчитування не буде перевищувати одиниці цього числа.
Одним з таких кодів є код Грея. Це непозиційний код, вага одиниці якого не визначається номером розряду. У цих кодах спостерігається симетричність відносно деякої осі відбиття – тобто ідентичність молодших розрядів. Звідси - “рефлексний код” (reflect – відбивати).
2. 2.5. Метод Шеннона-Фано
В цьому методі для кожного символа формується бітовий код, довжина якого залежить від частоти появи символа. Чим менша частота, тим довший код. Визначення частоти (ймовірності) символа буває статичне (на основі таблиці даних) та динамічне (коли відомості про ймовірність появи символів визначаються на основі обробки потоку даних). Статичний варіант використовується в архіваторах ARK, PKZIP.
Кодування здійснюється таким чином (рис. 1):
Всі символи записуються в таблицю по зменшенню їх частоти. Потім вони поділяються на дві групи так, щоб суми частот для отриманих груп були максимально близькі. Для першої групи перший біт коду встановлюється рівним 1, а для другої – 0.
Потім групи знову поділяємо на дві і визначаємо наступні розряди коду. Процес продовжується поки в групі не залишиться тільки один символ.
Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) будуть отримані різні коди для символів (рис. 2).
2.6. Метод Хаффмана.
Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках:
Всім символам ставиться у відповідність одна з вершин дерева.
Об’єднуємо дві вершини з мінімальними частотами і для нової вершини вказуємо сумарну частоту.
Переходимо на пункт 2, доки не об’єднаємо всі вершини.
Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0 (рис.3).
Текст програми:
#include <conio.h>
#include<stdio.h>
#include<io.h>
#include<math.h>
#include<stdlib.h>
struct idata{char a; int b; char c[8]; int d;}data[10],temp;
struct hf{int m; int n; int k[10];}huf[10],h1;
int n;
void sh_fano(int a, int b);
void huffm(void);
int nmb(char a);
void main(void){
clrscr();
int i,j,n1,n2;
char t,m1,m2;
FILE *in,*shf,*alph1,*hfm,*alph2;
n=0;
in=fopen("lj2.txt","r");
fread(&t,1,1,in);
while (!feof(in)){
j=0;
for(i=0;i<n;i++)
if(t==data[i].a) { data[i].b++; j++;}
if(j==0) {data[n].a=t; data[n].b++; n++;}
fread(&t,1,1,in);
}
for(i=0;i<(n-2);i++)
for(j=0;j<(n-1-i);j++)
if(data[j].b<data[j+1].b){
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
sh_fano(0,n-1);
shf=fopen("shf.txt","w");
fseek(in,0,0);
n1=0; n2=0; m1=0; m2=0;
fread(&t,1,1,in);
while(!feof(in)){
if(n1==8){
m1=m2; m2=0;
n1=n2; n2=0;
}
j=nmb(t);
for(i=0;i<data[j].d;i++)
if(n1<8) {m1|=data[j].c[i]<<(7-n1); n1++;}
else {m2|=data[j].c[i]<<(7-n2); n2++;}
if(n1==8) fwrite(&m1,1,1,shf);
fread(&t,1,1,in);
}
if(n1<8) fwrite(&m1,1,1,shf);
else fwrite(&m2,1,1,shf);
fclose(shf);
alph1=fopen("alph1.txt","w");
for(i=0;i<n;i++){
fprintf(alph1,"\n%2c%5d ",data[i].a,data[i].b);
for(j=0;j<data[i].d;j++)
if(data[i].c[j]==1) fprintf(alph1,"1");
else fprintf(alph1,"0");
}
fclose(alph1);
for(i=0;i<n;i++) data[i].d=0;
huffm();
alph2=fopen("alph2.txt","w");
for(i=0;i<n;i++){
fprintf(alph2,"\n%2c%5d ",data[i].a,data[i].b);
for(j=data[i].d-1;j>=0;j--)
if(data[i].c[j]==1) fprintf(alph2,"1");
else fprintf(alph2,"0");
}
fclose(alph2);
hfm=fopen("hfm.txt","w");
fseek(in,0,0);
n1=0; n2=0; m1=0; m2=0;
fread(&t,1,1,in);
while(!feof(in)){
if(n1==8){
m1=m2; m2=0;
n1=n2; n2=0;
}
j=nmb(t);
for(i=data[j].d-1;i>=0;i--)
if(n1<8) {m1|=data[j].c[i]<<(7-n1); n1++;}
else {m2|=data[j].c[i]<<(7-n2); n2++;}
if(n1==8) fwrite(&m1,1,1,shf);
fread(&t,1,1,in);
}
if(n1<8) fwrite(&m1,1,1,hfm);
else fwrite(&m2,1,1,hfm);
fclose(hfm);
fclose(in);
}
int nmb(char a){
int i;
for(i=0;i<n;i++)
if(data[i].a==a) return i;
}
void sh_fano(int a, int b){
int i,j,k,sum,sum1,sum2;
if(a==b) ;
else if((b-a)==1){
data[a].c[data[a].d]=1; data[a].d++;
data[b].c[data[b].d]=0; data[b].d++;
}
else{
sum=0; k=0;
for(i=a;i<(b+1);i++)
sum+=data[i].b;
sum=sum/2;
sum1=0; sum2=0;
for(i=a;i<(b+1);i++){
sum1=sum2;
sum2+=data[i].b;
if((sum2>sum)&&(k==0)){
if((abs(sum-sum1))<(abs(sum-sum2))) j=i-1;
else j=i;
k++;
}
}
for(i=a;i<(j+1);i++)
{data[i].c[data[i].d]=1; data[i].d++;}
sh_fano(a,j);
for(i=j+1;i<(b+1);i++)
{data[i].c[data[i].d]=0; data[i].d++;}
sh_fano((j+1),b);
}
}
void huffm(void){
int i,j,k,n1;
n1=n;
for(i=0;i<n;i++){
huf[i].m=data[i].b;
huf[i].n=1;
huf[i].k[0]=i;
}
while(n1>1){
for(i=0;i<huf[n1-2].n;i++){
k=huf[n1-2].k[i];
data[k].c[data[k].d]=1;
data[k].d++;
}
for(i=0;i<huf[n1-1].n;i++){
k=huf[n1-1].k[i];
data[k].c[data[k].d]=0;
data[k].d++;
}
for(i=0;i<huf[n1-1].n;i++)
huf[n1-2].k[huf[n1-2].n+i]+=huf[n1-1].k[i];
huf[n1-2].m+=huf[n1-1].m;
huf[n1-2].n+=huf[n1-1].n;
n1--;
for(i=0;i<(n1-1);i++)
for(j=0;j<(n1-i);j++)
if(huf[j].m<huf[j+1].m){
h1=huf[j];
huf[j]=huf[j+1];
huf[j+1]=h1;
}
}
}
Висновок:
Різновидності кодів: По формі представлення послідовні і паралельні коди.
По можливості виявлення та виправлення помилок прості (примітивні) і коректуючі коди.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
Арифметичні (числові, цифрові) коди базуються на системах числення і найчастіше використовуються в технічних системах.
Рівномірні прості цифрові коди.
Системи числення, на основі яких будуються цифрові коди, поділяються на позиційні і непозиційні.
Метод Шеннона-Фано: Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) будуть отримані різні коди для символів.
Метод Хаффмана: Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи.
Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0.
Виконуючи дану лабораторну роботу отримав практичні навики використання методів оптимального кодування.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора