Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Методи i засоби комп'ютерних інформаційних технологій
Варіант:
18
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра програмного забезпечення
Курсова робота
з курсу “Методи та засоби комп’ютерних
інформаційних технологій”
ЛЬВІВ – 2004
Зміст
Постановка задачі 3
Теоретичні відомості до завдання № 1 4
Розв’язання завдання № 1 5
Теоретичні відомості до завдання № 2 6
Розв’язання завдання № 2 7
Теоретичні відомості до завдання № 3 9
Розв’язання завдання № 3 10
Текст програми 12
Висновок 14
(Варіант № 18)
Постановка задачі
Завдання № 1
Задана матриця ймовірностей системи, об‘єднаної в одну з двох систем А і В.
P(A,B) = EMBED Equation.3
Визначити повні умовні ентропії 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)
Для нерівно ймовірних алфавітів ентропія на символ алфавіту
EMBED Equation.3 біт/символ, (5)
а кількість інформації в повідомленні, складеному з k нерівно ймовірних символів:
EMBED Equation.3 EMBED Equation.3 біт. (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) = EMBED Equation.3 P(bj)= EMBED Equation.3
- ) Визначемо умовні ймовірності p(ai/bj) = EMBED Equation.3
p(a1/ b1) = EMBED Equation.3 = 0,6 p(a1/ b2) =0 p(a1/ b3) =0
p(a2/ b1) = EMBED Equation.3 = 0,4 p(a2/ b2) = EMBED Equation.3 = 0,75 p(a2/ b3) = EMBED Equation.3 = 1
p(a3/ b1) = 0 p(a3/ b2) = EMBED Equation.3 = 0,25 p(a3/ b3) =0
P(ai/bj) = EMBED Equation.3 H(A/B) = EMBED Equation.3
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) = EMBED Equation.3
p(b1/a1) = EMBED Equation.3 = 1 p(b1/a2)= EMBED Equation.3 = 0,333 p(b1/a3) = 0
p(b2/a1) = 0 p(b2/a2)= EMBED Equation.3 = 0,5 p(b2/a3) = EMBED Equation.3 = 1
p(b3/a1) = 0 p(b3/a2)= EMBED Equation.3 = 0,167 p(b3/a3) = 0
EMBED Equation.3
P(bj/ai) = EMBED Equation.3 H(B/A) = EMBED Equation.3
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
Закони Кіргофа. Для написання законів Кіргофа необхідно прийняти додатній напрям струму в кожній вітці.
Перший закон Кіргофа – алгебраїчна сума всіх струмів, що сходяться в будь-якому вузлі, дорівнює нулю.
EMBED Equation.3
Струми, направлені від вузла, умовно приймаються додатніми, а направлені до нього – від’ємними (або навпаки).
Другий закон Кіргофа – алгебраїчна сума ЕРС замкнутого контуру дорівнює алгебраїчній сумі спадів напруг в ньому.
EMBED Equation.3
Напрям обходу контура вибирається довільно.
Розв’язання завдання № 2
Спочатку визначаємо загальний опір електричного кола:
I
I1 I2 I3
U R1 R2 R3
EMBED Equation.3 = EMBED Equation.3 = 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. Почергово фіксуємо два значення опорів і змінюємо третє.
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
Вищенаведені діаграми і графіки реалізовані засобами табличного процесора 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-ву систему числення. одержане число буде номером спотвореного символа.
Текст програми
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора