Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра програмного забезпечення
Курсова робота
з курсу “Методи та засоби комп’ютерних
інформаційних технологій”
ЛЬВІВ – 2004
Зміст
Постановка задачі 3
Теоретичні відомості до завдання № 1 4
Розв’язання завдання № 1 5
Теоретичні відомості до завдання № 2 6
Розв’язання завдання № 2 7
Теоретичні відомості до завдання № 3 9
Розв’язання завдання № 3 10
Текст програми 12
Висновок 14
(Варіант № 18)
Постановка задачі
Завдання № 1
Задана матриця ймовірностей системи, об‘єднаної в одну з двох систем А і В.
P(A,B) =
Визначити повні умовні ентропії H(B/A) і H(A/B).
Завдання № 2
Визначити еквівалентний опір трьох паралельних ланок для заданих параметрів схеми: R1 = 40 Ом; R2 = 50 Ом; R3 = 25 Ом; U = 1,5 B;
I
I1 I2 I3
U R1 R2 R3
Дослідити чутливість струму I3 від параметрів R1, R2, R3. Побудувати залежності ΔI від ΔR1, ΔR2, ΔR3.
Завдання № 3
Написати програму, яка формує перевірочна позиції коду Хемінга для довільного числа коректуючих позицій. Вивести на друк перевірочні позиції для перших п‘яти перевірок.
Теоретичні відомості до завдання № 1
Загальне число повідомлень, що не повторяються, і яке може бути складене з алфавіта m шляхом комбінування по n символів в повідомленні:
N = mn (1)
Невизначеність, що припадає на символ початкового алфавіта, складеного із рівноймовірних і незалежних символів:
H = log m (2)
Основа логарифму впливає лише на зручність обчислень. У випадку оцінки ентропії:
в війкових одиницях H = log2m біт/символ;
в десяткових одиницях H = lgm діт/символ, де log2m = 3.32lgm, 1 біт ≈ 0.3 діт;
в натуральних одиницях H = lnm нат/символ, де log2m = 1.443lnm, 1 біт = 0.693 нат.
Кількість інформації можна зобразити як добуток загального числа повідомлень k і середньої ентропії одного повідомлення:
I = kH біт (3)
Для випадків рівноймовірних і навзаємнезалежних символів вихідного алфавіту кількість інформації в k повідомленнях алфавіту m :
I = klog2m біт (4)
Для нерівно ймовірних алфавітів ентропія на символ алфавіту
біт/символ, (5)
а кількість інформації в повідомленні, складеному з k нерівно ймовірних символів:
біт. (6)
Кількість інформації визначається виключно характеристиками вихідного алфавіту. Об’єм – характеристика вторинного алфавіту. Об’єм інформації
Q = klcp, (7)
де lcp – середня довжина кодових слів вторинного алфавіту. Для рівномірних кодів (всі комбінації коду містять одинакову кількість розрядів)
Q = kn, (8)
де – довжина коду. Таким чином об’єм рівний кількості інформації, якщо lcp = H, тобто у випадку максимального інформаційного навантаження на символ повідомлення.
В загальному випадку ентропія – це кількість інформації на одиин стан системи. Якщо ентропія мала, то невизначеність відсутня.
Основні властивості ентропії:
Ентропія є неперервною і додатною функцією своїх аргументів (H>0).
Ентропія приймає мінімальне значення у двох випадках:
Якщо повідомлення формується за допомогою однієї ознаки, ймовірність появи якої рівне одиниці.
Якщо ймовірність i-ї ознаки приблизно рівна нулю.
Ентропія досягає максимуму, коли всі випадки рівноможливі.
Ентропія повідомлення, що складається з окремих повідомлень дорівнює сумі ентропій повідомлень [H(A,B) = H(A) +H(B)].
Розв’язання завдання № 1
Обчислимо безумовні ймовірності P(ai) та P(bj):
P(ai) = P(bj)=
- ) Визначемо умовні ймовірності p(ai/bj) =
p(a1/ b1) == 0,6 p(a1/ b2) =0 p(a1/ b3) =0
p(a2/ b1) == 0,4 p(a2/ b2) == 0,75 p(a2/ b3) == 1
p(a3/ b1) = 0 p(a3/ b2) == 0,25 p(a3/ b3) =0
P(ai/bj) = H(A/B) =
H(A/B) = - (0,5(0,6log20,6 + 0,4log20,4) + 0,4(0,75log20,75 + 0,25log20,25) + 0,1log20,1)) ≈ 0,485 + 0,324 ≈ 0,809 біт/символ.
- ) Визначемо умовні ймовірності p(bj/ai) =
p(b1/a1) = = 1 p(b1/a2)== 0,333 p(b1/a3) = 0
p(b2/a1) = 0 p(b2/a2)= = 0,5 p(b2/a3) = = 1
p(b3/a1) = 0 p(b3/a2)== 0,167 p(b3/a3) = 0
P(bj/ai) = H(B/A) =
H(A/B) = - 0,6(0,333log20,333 + 0,5log20,5 + 0,167log20,167) ≈
0,6(0,528 + 0,5 + 0,432) ≈ 0,876 біт/символ.
Теоретичні відомості до завдання № 2
Резистор - пасивний лінійний елемент, що володіє властивістю електричного опору. Струм і напруга електричного опору зв’язані законом Ома:
U = RI.
Величина, обернена до опору, називається електричною провідністю:
G = 1/R.
Активні лінійні елементи – це джерела електромагнітної енергії. Активні елементи поділяють на незалежні і залежні джерела.
Незалежні джерела можуть бути ідеальними чи реальними. Ідеальні джерела електрорушійної сили характеризуються напругою, яка не залежить від струму і характеризується електрорушійною силою Е. Внутрішній опір ідеального джерела ЕРС рівний нулю. Реальне джерело ЕРС має внутрішній опір і може бути відображене у вигляді послідовно з’єднаних ЕРС Е і опору R.
Ідеальне джерело струму: струм J джерела струму не залежить від напруги (внутрішня провідність джерела струму рівна нулю, опір джерела струму безмежно великий). Реальне джерело струму (з внутрішньою провідністю G = 1/R) може бути відображене у вигляді паралельної схеми, що містить джерело струму J , який чисельно дорівнює струму короткого замикання джерела струму і провідності G.
Перехід від схеми джерела ЕРС до еквівалентної схеми джерела струму за наступними співвідношеннями:
J = E/R, E = J/G, R = 1/G.
Закон Ома: на ділянці однорідного кола сила струму прямо пропорційна прикладеній напрузі та обернено пропорційна опору ділянки:
I = U/R
Закони Кіргофа. Для написання законів Кіргофа необхідно прийняти додатній напрям струму в кожній вітці.
Перший закон Кіргофа – алгебраїчна сума всіх струмів, що сходяться в будь-якому вузлі, дорівнює нулю.
Струми, направлені від вузла, умовно приймаються додатніми, а направлені до нього – від’ємними (або навпаки).
Другий закон Кіргофа – алгебраїчна сума ЕРС замкнутого контуру дорівнює алгебраїчній сумі спадів напруг в ньому.
Напрям обходу контура вибирається довільно.
Розв’язання завдання № 2
Спочатку визначаємо загальний опір електричного кола:
I
I1 I2 I3
U R1 R2 R3
= = 11,765 Ом
Використавши закони Ома і Кулона, запишемо:
I1=U/R1=1,5/40=0,0375 A; I=U/Rекв=0,1275 A;
I2=U/R2=1,5/50=0,03 A; I= I1+I2+I3=0,1275 A;
I3=U/R3=1,5/25=0,06A;
Дослідимо тепер залежність I3 від R1, R2, R3. Почергово фіксуємо два значення опорів і змінюємо третє.
ΔR1, Ом
ΔI3, A
-25
-0,0625
-20
-0,0375
-15
-0,0225
-10
-0,0125
-5
-0,00536
0
0
5
0,004167
10
0,0075
15
0,010227
20
0,0125
25
0,014423
ΔR2, Ом
ΔI3, A
-25
-0,03
-20
-0,02
-15
-0,01286
-10
-0,0075
-5
-0,00333
0
0
5
0,002727
10
0,005
15
0,006923
20
0,008571
25
0,01
ΔR3, Ом
ΔI3, A
-15
0,09
-12
0,055385
-9
0,03375
-6
0,018947
-3
0,008182
0
0
3
-0,00643
6
-0,01161
9
-0,01588
12
-0,01946
15
-0,0225
Вищенаведені діаграми і графіки реалізовані засобами табличного процесора Exel. У ньому ж відбувались всі обчислення опорів, струмів і напруг.
Теоретичні відомості до завдання № 3
Код Хемінга - це код, який виявляє і виправляє в слові всі одиничні помилки і виявляє подвійні помилки. Код Хемінга відноситься до систематичних кодів.
Систематичні коди -- це коди, в яких інформаційні та надлишкові символи розташовані на певних наперед визначених місцях. Код Хемінга, як і будь-який (n,k)-код, містить k інформаційних і (n-k) надлишкових символів. Надлишкова частина коду будується таким чином, щоб при декодуванні можна було б встановити не лише факт наявності помилок в даній комбінації, Але й вказати номер позиції, в якій сталась помилка. Це досягається шляхом багатократної перевірки прийнятої комбінації на парність. Кількість перевірок рівна кількості надлишкових символів. При кожній перевірці отримують двійковий контрольний символ. Якщо результат перевірки дає парне число, то контрольному символу присвоюється ”0”, якщо непарне - то “1”. В результаті всіх перевірок утворюється (n-k)-розрядне двійкове число, що вказує на номер спотвореного символа. Для виправлення помилки достатньо змінити значення даного символа на протилежне.
Необхідна кількість перевірочних символів виводиться з формули
.
Значення перевірочних символів і номери їх позицій за методом Хемінга встановлюється одночасно з вибором контрольних груп кодової комбінації.
Алгоритм кодування методом Хемінга:
Маємо вхідний потік нулів і одиниць:
k1 k2 k3 k4 k5 k6 ... kn
Нехай кодова довжина (довжина відрізків, на які ділиться потік)рівна 7 біт.Для того,щоб їх закодувати, потрібно на певні визначені місцявнести надлишкові символи,які потім допоможуть декодувати цей потік.
В коді Хемінга надлишкові символи ставляться на місцях,що є степенями числа 2. Тобто, вихідною стрічкою буде потік
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11
r1 r2 k1 r3 k2 k3 k4 r4 k5 k6 k7
де r[i] - надлишкові символи, k[i] - інформаційні символи
МЕТОДИКА ПОБУДОВИ.
Символи r[i] знаходяться наступним чином :
порядковий № в 2-ій СЧ
00001 b1 r1=k1 xor k2 xor k4 xor k5
00010 b2 r2=k1 xor k3 xor k4
00011 b3 k1
00100 b4 r3=k2 xor k3 xor k4
00101 b5 k2
00110 b6 k3
00111 b7 k4
01000 b8 r4=k5 xor k6 xor k7
01001 b9 k5
01010 b10 k6
01011 b11 k7
r1-це сума по модулю 2 тих k[i], в яких в першому розряді порядкового номера "1";
r2-це сума по модулю 2 тих k[i], в яких в другому розряді порядкового номера "1";
r3- третьому;
r4- четвертому;
Алгоритм декодування методом Хемінга:
Для декодування записують систему рівнянь наступного вигляду
r1 xor k1 xor k2 xor k4 xor k5 xor k7 = 0
r2 xor k1 xor k3 xor k4 xor k6 xor k7 = 0
r3 xor k2 xor k3 xor k4 xor = 0
r4 xor k5 xor k6 xor k7 = 0
1 xor 1 = 0
0 xor 0 = 0
1 xor 0 = 1
0 xor 1 = 1
Якщо кодове слово правильне, то система рівнянь виконується. Якщо в кодовому слові є помилка, то права частина системи буде складатись не лише з нулів. Праву частину називають синдромом або розпізнавачем помилки. Щоб знайти помилку, необхідно прочитати синдром знизу вверх і перевести його в 10-ву систему числення. одержане число буде номером спотвореного символа.
Текст програми
uses drivers,crt,dos;
var ev:tevent;
procedure menu;
begin
initevents; showmouse; textbackground(9);
gotoxy(1,1);write(' ');
gotoxy(1,2);write(' ');
gotoxy(1,3);write(' ');
textbackground(0);
gotoxy(28,1);write('+====================+');
gotoxy(28,2);write('| Коди Хеммiнга |');
gotoxy(28,3);write('+====================+');
gotoxy(58,5); write('+====================+');
gotoxy(58,6); write('| Кодування |');
gotoxy(58,7); write('+====================+');
gotoxy(58,8); write('| Декодування |');
gotoxy(58,9); write('+====================+');
gotoxy(58,10);write('| Про коди Хеммiнга |');
gotoxy(58,11);write('+====================+');
gotoxy(58,12);write('| Вихiд з програми |');
gotoxy(58,13);write('+====================+');
textbackground(9);
gotoxy(1,23);write(' ');
gotoxy(1,24);write(' ');
gotoxy(1,25);write(' ');
textbackground(0);
end;
procedure code;
var s:string;
i,r1,r2,r3,r4,r5,n,k:word;
a:array[1..20] of word;
label lab1,lab2;
begin
window (4,5,54,22); clrscr;
for i:=1 to 20 do a[i]:=0;
writeln('+=====+======================+');
writeln('| Код | |');
writeln('+=====+=====+================+');
writeln('| n | ? |');
writeln('| k | ? |');
writeln('| r1 | ? |');
writeln('| r2 | ? |');
writeln('| r3 | ? |');
writeln('| r4 | ? |');
writeln('| r5 | ? |');
writeln('+=====+=====+====================+');
writeln('| Код | | ');
write ('+=====+==========================+');
gotoxy(9,2); readln(s); n:=length(s); k:=3;
if n>4 then inc(k);
if n>11 then inc(k);
for i:=1 to n do a[i]:=word(s[i])-48;
gotoxy(10,4); write(n); gotoxy(10,5); write(k);
r1:=a[1] xor a[2] xor a[4] xor a[5] xor a[7] xor a[9] xor a[11]
xor a[12] xor a[14]; gotoxy(10,6); write(r1);
r2:=a[1] xor a[3] xor a[4] xor a[6] xor a[7] xor a[10] xor a[11]
xor a[13] xor a[14]; gotoxy(10,7); write(r2);
r3:=a[2] xor a[3] xor a[4] xor a[8] xor a[9] xor a[10] xor a[11]
xor a[15]; gotoxy(10,8); write(r3); if n<5 then goto lab1;
r4:=a[5] xor a[6] xor a[7] xor a[8] xor a[9] xor a[10] xor a[11];
gotoxy(10,9); write(r4); if n<12 then goto lab1;
r5:=a[12] xor a[13] xor a[14] xor a[15]; gotoxy(10,10); write(r5);
lab1:
insert (char(r1+48),s,1); insert (char(r2+48),s,2); insert (char(r3+48),s,4);
if n<5 then goto lab2; insert (char(r4+48),s,8);
if n<12 then goto lab2; insert (char(r5+48),s,16);
lab2:
gotoxy(10,12); write(s); end;
procedure decode;
var s:string;
i,r1,r2,r3,r4,r5,c1,c2,c3,c4,c5,n,k:word;
a:array[1..30] of word;
label lab1,lab2;
begin
window (4,5,54,22); clrscr;
for i:=1 to 30 do a[i]:=0;
writeln('+=====+==========================+');
writeln('| Код | |');
writeln('+=====+=====+====================+');
writeln('| n | ? |');
writeln('| k | ? |');
writeln('| c1 | ? |');
writeln('| c2 | ? |');
writeln('| c3 | ? |');
writeln('| c4 | ? |');
writeln('| c5 | ? |');
writeln('+=====+=====+====================+');
writeln('| Код | | ');
write ('+=====+==========================+');
gotoxy(9,2); readln(s); n:=length(s); k:=3;
for i:=1 to n do a[i]:=word(s[i])-48;
r1:=a[1]; r2:=a[2]; r3:=a[4]; r4:=a[8]; r5:=a[16];
if n>7 then inc(k);
if n>15 then inc(k);
gotoxy(10,4); write(n); gotoxy(10,5); write(k);
delete (s,1,1); delete (s,1,1); delete (s,2,1);
if n<8 then goto lab2;
delete (s,5,1);
if n<16 then goto lab2;
delete (s,12,1);
lab2:
for i:=1 to n do a[i]:=0;
for i:=1 to n-k do a[i]:=word(s[i])-48;
c1:=r1 xor a[1] xor a[2] xor a[4] xor a[5] xor a[7] xor a[9] xor a[11]
xor a[12] xor a[14]; gotoxy(10,6); write(c1);
c2:=r2 xor a[1] xor a[3] xor a[4] xor a[6] xor a[7] xor a[10] xor a[11]
xor a[13] xor a[14]; gotoxy(10,7); write(c2);
c3:=r3 xor a[2] xor a[3] xor a[4] xor a[8] xor a[9] xor a[10] xor a[11]
xor a[15]; gotoxy(10,8); write(c3); if n<8 then goto lab1;
c4:=r4 xor a[5] xor a[6] xor a[7] xor a[8] xor a[9] xor a[10] xor a[11];
gotoxy(10,9); write(c4); if n<16 then goto lab1;
c5:=r5 xor a[12] xor a[13] xor a[14] xor a[15]; gotoxy(10,10); write(c5);
lab1:
gotoxy(10,12); write(s); end;
procedure info;
var ev1:tevent;
var x,y,j,k,l:integer;
i:word;
s:array[1..25] of string;
begin
window (4,5,54,22); clrscr;
write ('+=================================================+');gotoxy(1,17);
write ('+=================================================+');
s[1]:= '| Код Хеммiнга - це код, який виявляе i виправляе |';
s[2]:= '| в словi всi одиничнi помилки i виявляе всi |';
s[3]:= '| подвiйнi помилки. Код Хеммiнга вiдносять до |';
s[4]:= '| систематичних кодiв. Систематичнi коди - це |';
s[5]:= '| коди, в яких iнформацйнi та надлишковi символи |';
s[6]:= '| розташованi на певних наперед визначених мiсцях.|';
s[7]:= '| Код Хеммiнга, як i будь-який (n-k) код, мiстить |';
s[8]:= '| k iнформацйних i (n-k) надлишкових символiв. |';
s[9]:= '| Надлишкова частина коду будуеться таким чином, |';
s[10]:='| щоб при декодуваннi можна було б встановити не |';
s[11]:='| лише факт наявностi помилок в данiй комбiнацiх, |';
s[12]:='| але й вказати номер позицiх, в якiй сталась |';
s[13]:='| помилка. Це досягаеться шляхом багатократнох |';
s[14]:='| перевiрки прийнятох комбiнацiх на парнiсть. |';
s[15]:='| Кiлькiсть перевiрок рiвна кiлькостi надлишкових |';
s[16]:='| символiв. При кожнiй перевiрцi отримують |';
s[17]:='| двiйковий контрольний символ. Якщо результат |';
s[18]:='| перевiрки дае парне число, то контрольному |';
s[19]:='| символу присвоюеться "0", якщо непарне - то "1".|';
s[20]:='| В результатi всiх перевiрок утворюеться (n-k) |';
s[21]:='| розрядне двiйкове число, що вказуе на номер |';
s[22]:='| спотвореного символа. Для виправлення помилки |';
s[23]:='| достатньо змiнити значення даного символа на |';
s[24]:='| протилежне. |';
window (4,6,54,21);
for i:=1 to 15 do write(s[i]);
j:=0; k:=-1;
repeat
GetMouseEvent(ev1);
y:= mousewhere.y;l:=k;
if y>j then inc(k);
if y<j then dec(k);
if k>9 then k:=9;
if k<0 then k:=0;
if l<>k then begin gotoxy(1,1);
for i:=1+k to 15+k do write(s[i]); end; j:=y;
until ev1.buttons=$02;
end;
procedure select(var event:tevent);
var x,y:integer;
begin
x:= mousewhere.x; y:= mousewhere.y;
if (Event.Buttons=$01) then
if ((x>58) and (x<78)) then
case y of
5 : code;
7 : decode;
9 : info;
11: halt;
end; end;
begin
clrscr; {highvideo;} textbackground(0);
window(1,1,80,25); clrscr;
menu; gotoxy(1,1);
repeat
GetMouseEvent(ev); select(ev);
until keypressed;
end.
Висновок
В даній курсовій роботі розглянуті одні з основних розділів науки, яка вивчає інформаційні технології. Розв’язані задачі торкаються таких тем як кількісна оцінка інформації, основні закони і методи розрахунку лінійних електричних ланцюгів, виявлення і виправлення помилок в повідомленнях. Таким чином, очевидно, що для вирішення реальних проблем розробки, проектування, реалізації інформаційних технологій необхідні знання в багатьох розділах математики, електротехніки, програмування і суміжних науках. Важливим висновком є те, що разом з теоретичною базою, для розв’язання сучасних задач необхідними є ґрунтовні прикладні знання і навички.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора