Розрахунок інформаційних характеристик каналу зв'язку

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХПІ”
Кафедра “Обчислювальна техніка та програмування”
Курсова розрахункова робота
з курсу “Теорія інформації та кодування”
 
Виконав:
студент групи ччч-ччч
ччччччччччч.
Перевірив:
доц. чччч.
Харків 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·log20,31+0,11·log20,11+2·0,02·log20,02++2·0,01·log20,01+3·0,03log20,03+2·0,05·log20,05+0,09·log20,09+2·0,07·log20,07+0,06·log20,06+0,04·log20,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 k2a1 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 = 1 1 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.

Додання
Програма розрахунку інформаційних характеристик каналузв'язку
{Расчетноезадание по курсу ТИК}
ProgramWork20;
UsesCRT;
Constn=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;
Fori:=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);
ifi 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);
{==Определим вероятности появления символов на входе приемника информации ==}
Forj:=1 to n do
Begin
s:=0;
Fori:=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;
Fori:=1 to n do
Begin
Textcolor(15);
Write(arr_py[i]:7:4,'':2);
Write(f,arr_py[i]:7:4,'':2);
ifi mod 8 =0 then
begin
writeln;
writeln(f);
end;
End;
Forj:=1 to n do
Begin
write(f,'p(y',j,')=');
s:=0;
Fori:=1 to n do
begin
s:=s+arr_px[i]*arr_x[j,i];
ifarr_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);
Fori:=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=');
fori:=1 to n do
write(f,'+',arr_py[i]:2:4,'·','log2(',arr_py[i]:2:4,')');
write(f,'=-(');
s:=0;
Fori:=1 to n do
Begin
ds:=arr_py[i]*ln(arr_py[i])/ln(2);
Write(ds:7:3);Write(f,ds:7:3);
ifi 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)=[');
Fori:=1 to n do
Begin
s:=0;
write(f,'+',arr_px[i]:1:2,'·(');
Forj:=1 to n do
IFarr_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.11020.0208 0.0117 0.0297 0.0210 0.0502 0.0888
0.0701 0.06040.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.