МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХПІ”
Кафедра “Обчислювальна техніка та програмування”
Курсова розрахункова робота
з курсу “Теорія інформації та кодування”
Виконав:
студент групи ччч-ччч
ччччччччччч.
Перевірив:
доц. чччч.
Харків 2007
Зміст
Вступ
Завдання
Розрахунок інформаційних характеристик каналу зв'язку
Побудова коду для передачі повідомлень
Висновок
Додання
Програма розрахунку інформаційних характеристик каналу зв'язку
Підсумок роботи програми
Література
Вступ
Метою виконання розрахункового курсового завдання є придбання навичок по розрахунку основних інформаційних характеристик каналу зв'язку та побудови кодів для передачі інформації по каналу зв'язку, а також засвоєння процедури кодування, декодування та оцінка ефективності кодів. Для розрахунку інформаційних характеристик каналу зв'язку доцільно сконструювати програму на алгоритмічній мові Паскаль.
Завдання
По каналу зв'язку передаються повідомлення, що являють послідовність шістнадцятирічних цифр імовірності яких відповідно дорівнюють:
p(1)=0,31; p(2)=0,11; p(3)=0,02; p(4)=0,01; p(5)=0,03; p(6)=0,02; p(7)=0,05; p(8)=0,09; p(9)=0,07; p(10)=0,06; p(11)=0,07; p(12)=0,05; p(13)=0,03; p(14)=0,04; p(15)=0,01; p(16)=0,03.
Канальна матриця, що визначає втрати інформації в каналі зв'язку має вид: P(y/x)=
Визначити:
1 Ентропію джерела інформації - H(X)
2 Безумовну ентропію приймача інформації - H(Y).
3 Загальну умовну ентропію - H(Y/X).
4 Швидкість передачі інформації, якщо час передачі одного символу первинного алфавіту дорівнює 0,25мкс
5 Визначити втрати інформації в каналі зв'язку при передачі 1500 символів алфавіту.
6 Середню кількість прийнятої інформації.
7 Побудувати код за методом Хемінга для передачі повідомлень в вигляді чотирьохрозрядного двійкового коду із знаходженням і виправленням однократних помилок.
8 Показати процедуру кодування, декодування і виправлення помилки.
9 Привести схему кодера и декодера для коду Хэмінга.
Розрахунок інформаційних характеристик каналу зв'язку
Визначимо ентропію джерела інформації. Ентропія джерела повідомлень розраховується по формулі:
-(0,31·log2
0,31+0,11·log2
0,11+2·0,02·log2
0,02+ +2·0,01·log2
0,01+3·0,03log2
0,03+2·0,05·log2
0,05+0,09·log2
0,09+2·0,07·log2
0,07+0,06·log2
0,06+0,04·log2
0,04)= 3,399 біт/симв.
Визначимо імовірність появи символів на вході приймача за допомогою умовних ймовірностей
=p(x1
)·p(y1
/x1
)+p(x2
)·p(y1
/x2
)+p(x3
)·p(y1
/x3
)+p(x4
)·p(y1
/x4
)+p(x5
)·p(y1
/x5
)+
+p(x6
)·p(y1
/x6
)+p(x7
)·p(y1
/x7
)+p(x8
)·p(y1
/x8
)+p(x9
)·p(y1
/x9
)+p(x10
)·p(y1
/x10
)+
+p(x11
)·p(y1
/x11
)+p(x12
)·p(y1
/x12
)+p(x13
)·p(y1
/x13
)+p(x14
)·p(y1
/x14
)+p(x15
)·p(y1
/x15
)+
+p(x16
)·p(y1
/x16
) = 0,31·0,98+0,11·0,01+0,02·0,01=0,3051
p(y2)=0,31·0,01+0,11·0,97+0,02·0,02=0,1102;
p(y3)=0,11·0,01+0,02·0,98+0,01·0,01=0,0208;
p(y4)=0,11·0,01+0,02·0,02+0,01·0,94+0,03·0,02+0,02·0,01=0,0117;
p(y5)=0,01·0,01+0,03·0,98+0,02·0,01=0,0297;
p(y6)=0,01·0,01+0,03·0,01+0,02·0,96+0,05·0,01+0,09·0,01=0,0210;
p(y7)=0,03·0,01+0,02·0,02+0,05·0,94+0,09·0,02+0,07·0,01=0,0502;
p(y8)=0,05·0,02+0,09·0,96+0,07·0,02=0,0888;
p(y9)=0,09·0,01+0,07·0,98+0,06·0,01=0,0701;
p(y10)=0,09·0,01+0,07·0,01+0,06·0,96+0,07·0,01+0,05·0,01=0,0604;
p(y11)=0,07·0,01+0,06·0,01+0,07·0,96+0,05·0,01+0,03·0,01=0,0693;
p(y12)=0,06·0,01+0,07·0,01+0,05·0,95+0,03·0,02+0,04·0,01=0,0498;
p(y13)=0,05·0,02+0,03·0,96+0,04·0,02=0,0306;
p(y14)=0,05·0,01+0,03·0,02+0,04·0,94+0,01·0,02+0,03·0,01=0,0392;
p(y15)=0,03·0,01+0,04·0,02+0,01·0,95+0,03·0,02=0,0112;
p(y16)=0,04·0,01+0,01·0,01+0,03·0,98=0,0299;
Перевірка: Так як прийняті повідомлення становлять повну групу явищ то їх сумарна імовірність дорівнює 1.
0,3051+0,1102+0,0208+0,0117+0,0297+0,0210+0,0502+0,0888+
+0,0701+0,0604+0,0693+0,0498+0,0306+0,0392+0,0112+0,0299= 1,00;
Визначимо ентропію приймача інформації. Ентропія приймача повідомлень розраховується по формулі:
= 0,3051·log2(0,3051)+0,1102·log2(0,1102)+
+0,0208·log2(0,0208)+0,0117·log2(0,0117)+0,0297·log2(0,0297)+
+0,0210·log2(0,0210)+0,0502·log2(0,0502)+0,0888·log2(0,0888)+
+0,0701·log2(0,0701)+0,0604·log2(0,0604)+0,0693·log2(0,0693)+
+0,0498·log2(0,0498)+0,0306·log2(0,0306)+0,0392·log2(0,0392)+
+0,0112·log2(0,0112)+0,0299·log2(0,0299)=
= -(-0,523 -0,351 -0,116 -0,075 -0,151 -0,117 -0,217 -0,310 -0,269 -0,245 -0,267 -0,216 -0,154 -0,183 -0,073 -0,151)=3,416 біт/симв.
Загальна умовна ентропія розраховується по формулі:
=[0,31·(0,98·log2(0,98)+2·0,01·log2(0,01))+
+0,11·(0,01·log2(0,01)+0,97·log2(0,97)+0,02·log2(0,02))+
+0,02·(0,98·log2(0,98)+2·0,01·log2(0,01))+
+0,01·(2·0,01·log2(0,01)+2·0,02·log2(0,02)+0,94·log2(0,94))+
+0,03·(2·0,01·log2(0,01)+0,98·log2(0,98))+
+0,02·(4·0,01·log2(0,01)+0,96·log2(0,96))+
+0,05·(2·0,01·log2(0,01)+2·0,02·log2(0,02)+0,94·log2(0,94))+
+0,09·(2·0,02·log2(0,02)+0,96·log2(0,96))+
+0,07·(2·0,01·log2(0,01)+0,98·log2(0,98))+
+0,06·(4·0,01·log2(0,01)+0,96·log2(0,96))+
+0,07·(4·0,01·log2(0,01)+0,96·log2(0,96))+
+0,05·(3·0,01·log2(0,01)+0,95·log2(0,95)+0,02·log2(0,02))+
+0,03·(2·0,02·log2(0,02)+0,96·log2(0,96))+
+0,04·(2·0,01·log2(0,01)+2·0,02·log2(0,02)+0,94·log2(0,94))+
+0,01·(0,01·log2(0,01)+2·0,02·log2(0,02)+0,95·log2(0,95))+
+0,03·(2·0,01·log2(0,01)+0,98·log2(0,98))]=0,248 біт/симв.
Визначимо швидкість передачі інформації яка являє середню кількість інформації яка передається по каналу зв'язку за одиницю часу та розраховується по формулі:
С=V[H(Y)-H(Y/X)]=V[H(X)-H(X/Y)]==1/(0,25·103
)·(3,416-0,248)=12,67 Кбіт/с.
Визначимо втрати інформації в каналі зв'язку при передачі 1500 символів алфавіту
k H (Y/X)=1500·0,248 =371,8 бит.
Визначимо середню кількість прийнятої інформації:
I=k[H(Y)-H(Y/X)]=k [H(X)-H(X/Y)]==1500·(3,416-0,248)=4,752 Кбіт.
Побудова коду для передачі повідомлень
Постановка задачі
Побудувати код за методом Хемінга з виправленням однократної помилки для передачі повідомлень у виді послідовності 16-річных цифр представлених у виді 4-розрядних двійкових слів. Показати процес кодування, декодування і виправлення одиночної помилки на прикладі інформаційного слова 5 – [0101].
Порядок побудови коду за методом Хемінга
1. Первинне кодування. Визначимо інформаційні комбінації (слова) лінійного коду, як повний 4-х розрядний двійковий код зі старшинством розрядів праворуч наліво, відповідно до їх надходження на вхід декодера.
0) 0000 4) 0100 8) 1000 C) 1100
1) 0001 5) 0101 9) 1001 D) 1101
2) 0010 6) 0110 A) 1010 E) 1110
3) 0011 7) 0111 B) 1011 F) 1111
2. Визначимо довжину кодової комбінації по заданій довжині інформаційного слова (k = 4), використовуючи співвідношення:
m = [log2 {(k+1)+ [log2(k+1)]}]=[log2 {(4+1)+ [log2(4+1)]}]=3,
при цьому n = k + m = 7, тобто одержали (7, 4) -код.
Для виправлення одиночної помилки (s = 1) мінімальне кодова відстань дорівнює d0
= 2s+1 = 3.
3. Визначимо структуру кодової комбінації.
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
| к |
к |
а1 |
к |
а2 |
а3 |
а4 |
| b1 |
b2 |
b3 |
b4 |
b5 |
b6 |
b7 |
Контрольні біти розположені на 1, 2, 4... місцях.
4. Визначимо значення контрольних бітів.
Складемо матрицю:
k1 k2 a1 k3 a2 a3 a4
Перевірки:
к3“а2“а3“а4
к2“а1“а3“а4
к1“а1“а2“а4
Тобто контрольні біти:
5 – [0101]
к3 = а2“а3“а4 = 1“0“1 = 0
к2 = а1“а3“а4 = 0“0“1 = 1
к1 = а1“а2“а4 = 0“1“1 = 0
5. Кодування.
Отримали закодоване слово:
| F = |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
| k1 |
k2 |
a1 |
k3 |
a2 |
a3 |
a4 |
Введемо в закодоване слово помилку в 3 біті:
F` = 0110101
6. Декодування.
Візьмемо перевірки:
к3“а2“а3“а4 = 0“1“0“1 = 0
к2“а1“а3“а4 = 1“1“0“1 = 1
к1“а1“а2“а4 = 0“1“1“1 = 1
Отримали синдром помилки Sп = 011, що вказує на помилку в третьому біті – його необхідно інвертувати.
7. Схема кодера.
Розробимо схему кодера (Рис. 1):
Рис. 1 Схема кодера
8. Схема декодера.
Розробимо схему декодера (Рис. 2):
Рис. 2 Схема декодера
">Висновок
В наслідок виконання завдання розраховані основні інформаційні характеристики каналу зв'язку для чого розроблена відповідна програма на алгоритмічній мові Паскаль, яка наведена в додатку.
Побудовано код за методом Хемінга для передачі повідомлень з виявленням і виправленням однократних помилок. Порядок побудови коду, процес кодування, декодування, виявлення та виправлення помилок розглянуто на прикладі інформаційного слова 0101.
Додання
Програма розрахунку інформаційних характеристик каналу зв'язку
{Расчетное задание по курсу ТИК}
Program Work20;
Uses CRT;
Const n=16;
arr_px:array[1..n] of real =
(0.31, 0.11, 0.02, 0.01, 0.03, 0.02, 0.05, 0.09, 0.07, 0.06, 0.07, 0.05, 0.03, 0.04, 0.01, 0.03);
arr_x:array[1..n,1..n] of real =
(( 0.98,0.01,0.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
( 0.01,0.97,0.02, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
( 0,0.01,0.98,0.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
( 0,0.01,0.02,0.94,0.02,0.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0,0.01,0.98,0.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0,0.01,0.01,0.96,0.01,0.01, 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0,0.01,0.02,0.94,0.02,0.01, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0,0.02,0.96,0.02, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0,0.01,0.98,0.01, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0,0.01,0.01,0.96,0.01,0.01, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0,0.01,0.01,0.96,0.01,0.01, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0, 0,0.01,0.01,0.95,0.02,0.01, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0.02,0.96,0.02, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0.01,0.02,0.94,0.02,0.01),
( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0.01,0.02,0.95,0.02),
( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0.01,0.01,0.98));
Type
vec=array[1..n] of real;
Var
f :text;
arr_S,arr_py :vec;
s,ds,H,HX,HY,HYX,Ik,Ck,V,T,Ic,Cn :real;
i,j :byte;
k :integer;
BEGIN
Assign(f,'d:work20.txt');
Rewrite(f);
ClrScr;
T:=0.25E-3;
V:=1/T;
K:=1500;
Writeln(f,'Решение:');
Writeln(f);
{============ Определим энтропию источника информации ===============}
Textcolor(5);
Writeln('1.Энтропия источника информации равна:');
Writeln(f,'Энтропия источника информации равна:');
Writeln('Промежуточные суммы:'); Writeln(f,'Промежуточные суммы:');
Readkey;
TextColor(15);
s:=0;
For i:=1 to n do
Begin
ds:=arr_px[i]*ln(arr_px[i])/ln(2); s:=s+ds;
Write(ds:7:3);
Write(f,ds:7:3);
if i mod 8 =0 then
begin
writeln;
writeln(f);
end;
End;
Writeln;
Writeln('Результат:');
Writeln(f,'Результат:');
HX:=-s;
Writeln(f);
TextColor(15);
Writeln('H(X)=',HX:6:3,' бит/симв.');
Writeln(f,' H(X)= ',HX:6:3,' бит/симв.');
Writeln(f);
{== Определим вероятности появления символов на входе приемника информации ==}
For j:=1 to n do
Begin
s:=0;
For i:=1 to n do
s:=s+arr_px[i]*arr_x[j,i];
arr_py[j]:=s;
End;
Textcolor(5);
Writeln('2.Вероятности появления символов на входе приемника информации равны:');
Writeln(f,'Вероятности появления символов на входе приемника информации равны:');
Readkey;
For i:=1 to n do
Begin
Textcolor(15);
Write(arr_py[i]:7:4,' ':2);
Write(f,arr_py[i]:7:4,' ':2);
if i mod 8 =0 then
begin
writeln;
writeln(f);
end;
End;
For j:=1 to n do
Begin
write(f,'p(y',j,')=');
s:=0;
For i:=1 to n do
begin
s:=s+arr_px[i]*arr_x[j,i];
if arr_x[j,i]<>0 then
begin
write('+',arr_px[i]:2:2,'·',arr_x[j,i]:2:2);
write(f,'+',arr_px[i]:2:2,'·',arr_x[j,i]:2:2);
end;
end;
arr_py[j]:=s;
Writeln('=',s:5:4);
Writeln(f,'=',s:5:4);
End;
{=== Проверка ===}
s:=0;
Writeln(f);
Writeln(f,' Проверка:',' ':8);
Write(f,'S=');
Writeln;
Write(' Проверка:',' ':8);
For i:=1 to n do
begin
write(f,'+',arr_py[i]:2:4);
s:=s+arr_py[i];
end;
Writeln('s=',s:6:2);Writeln(f,'=',s:6:2,';');
Writeln(f);
{=============== Oпределим энтропию приемника информации ==============}
TextColor(5);
Writeln('Энтропия приемника информации равна:');
Writeln(f,'Энтропия приемника информации равна:');
Writeln('Промежуточные суммы:');
Writeln(f,'Промежуточные суммы:');
Readkey;
Textcolor(15);
write(f,'Entrop=');
for i:=1 to n do
write(f,'+',arr_py[i]:2:4,'·','log2(',arr_py[i]:2:4,')');
write(f,'= -(');
s:=0;
For i:=1 to n do
Begin
ds:=arr_py[i]*ln(arr_py[i])/ln(2);
Write(ds:7:3);Write(f,ds:7:3);
if i mod 8 =0 then writeln;
s:=s+ds;
End;
HY:=-s;
write(f,')=',HY:2:3);
Writeln;
Writeln(f);
Writeln('Результат:');
Writeln(f,'Результат:');
TextColor(15);
Writeln('H(Y)=',HY:6:3,' бит/симв.');
Writeln(f,' H(Y)=',HY:6:3,' бит/симв.');
Writeln(f);
{================ Определим общую условную энтропию ==================}
TextColor(5);
Writeln('3.Общая условная энтропия равна:');
Writeln(f,'Общая условная энтропия равна:');
Writeln('Промежуточные суммы:');
Writeln(f,'Промежуточные суммы:');
Readkey;
Textcolor(15);
H:=0;
write(f,'H(Y/X)=[');
For i:=1 to n do
Begin
s:=0;
write(f,'+',arr_px[i]:1:2,'·(');
For j:=1 to n do
IF arr_x[i,j]<>0 then
Begin
ds:=arr_px[i]*arr_x[i,j]*ln(arr_x[i,j])/ln(2);
Write(ds:7:3);Write(f,'+',arr_x[i,j]:1:2,'·log2(',arr_x[i,j]:1:2,')');
s:=s+ds;
End;
write(f,')');
Writeln;
H:=H+s;
End;
HYX:=-H;
write(f,']=',HYX:2:3);
Writeln;
Writeln(f);
Writeln('Результат:');
Writeln(f,'Результат:');
TextColor(15);
Writeln(' H(Y/X)=',HYX:6:3,' бит/симв.');
Writeln(f,' H(Y/X)=',HYX:6:3,' бит/симв.');
Writeln;
Writeln(f);
{============== Определим скорость передачи информации ==============}
TextColor(5);
Writeln('4.Скорость передачи инфoрмации равна:');
Writeln(f,'Скорость передачи информации равна:');
Writeln(f);
Readkey;
Ck:=V*(HY-HYX);
TextColor(15);
Writeln(' Ck=V[H(Y)-H(Y/X)]=V[H(X)-H(X/Y)]=',Ck:10,' бит/с');
Writeln(f,' Ck=V[H(Y)-H(Y/X)]=V[H(X)-H(X/Y)]=',Ck:10,' бит/с');
Writeln(f);
{== Определим потери в канале связи при передаче 500 символов алфавита ==}
TextColor(5);
Writeln('Потери в канале связи при передаче ',k,' символов алфавита равны:');
Writeln(f,'Потери в канале связи при передаче ',k,' символов алфавита равны:');
Writeln(f);
Readkey;
Ik:=k*HYX;
TextColor(15);
Writeln(' Ik=k*H(Y/X)=',Ik:10,' бит');
Writeln(f,' Ik=k*H(Y/X)=',Ik:10,' бит');
Writeln(f);
{========== Определим среднее количество принятой информации ==========}
TextColor(5);
Writeln('Среднее количество принятой информации равно:');
Writeln(f,'Среднее количество принятой информации равно:');
Writeln(f);
Readkey;
Ic:=k*(HY-HYX);
TextColor(15);
Writeln(' Ic=k*[H(Y)-H(Y/X)]=k*[H(X)-H(X/Y)]=',Ic:10,' бит');
Writeln(f,' Ic=k*[H(Y)-H(Y/X)]=k*[H(X)-H(X/Y)]=',Ic:10,' бит');
Writeln(f);
Readkey;
Close(f);
END.
Підсумок роботи програми
1.Энтропия источника информации равна:
Промежуточные суммы:
-0.524 -0.350 -0.113 -0.066 -0.152 -0.113 -0.216 -0.313
-0.269 -0.244 -0.269 -0.216 -0.152 -0.186 -0.066 -0.152
Результат:
H(X)= 3.399 бит/симв.
2.Вероятности появления символов на входе приемника информации равны:
0.3051 0.1102 0.0208 0.0117 0.0297 0.0210 0.0502 0.0888
0.0701 0.0604 0.0693 0.0498 0.0306 0.0392 0.0112 0.0299
Проверка: s= 1.00
Энтропия приемника информации равна:
Промежуточные суммы:
-0.523 -0.351 -0.116 -0.075 -0.151 -0.117 -0.217 -0.310
-0.269 -0.245 -0.267 -0.216 -0.154 -0.183 -0.073 -0.151
Результат:
H(Y)= 3.416 бит/симв.
3.Общая условная энтропия равна:
Промежуточные суммы:
-0.009 -0.021 -0.021
-0.007 -0.005 -0.012
-0.001 -0.001 -0.001
-0.001 -0.001 -0.001 -0.001 -0.001
-0.002 -0.001 -0.002
-0.001 -0.001 -0.001 -0.001 -0.001
-0.003 -0.006 -0.004 -0.006 -0.003
-0.010 -0.005 -0.010
-0.005 -0.002 -0.005
-0.004 -0.004 -0.003 -0.004 -0.004
-0.005 -0.005 -0.004 -0.005 -0.005
-0.003 -0.003 -0.004 -0.006 -0.003
-0.003 -0.002 -0.003
-0.003 -0.005 -0.003 -0.005 -0.003
-0.001 -0.001 -0.001 -0.001
-0.002 -0.002 -0.001Результат:
H(Y/X)= 0.248 бит/симв.
4. Скорость передачи инфoрмации равна:
Ck=V[H(Y)-H(Y/X)]=V[H(X)-H(X/Y)]= 1.267E+04 бит/с
5.Потери в канале связи при передаче 1500 символов алфавита равны:
Ik=k*H(Y/X)= 3.718E+02 бит
6.Среднее количество принятой информации равно:
Ic=k*[H(Y)-H(Y/X)]=k*[H(X)-H(X/Y)]= 4.752E+03 бит
Література
1 Гойфман Э.Ш., Лосев Ю.И. Передача информации в АСУ. – М.: Связь, 1976.
2 Колесник В.Д., Полтырев Г.Ш. Курс теории информации. –М.: Наука, 1982.
3 Цымбал В.П. Теория информации и кодирование. –М.: Высш. шк., 1986.
4 Гринченко А.Г. Теория информации и кодирование: Учебн. пособие. – Харьков: ХПУ, 2000.