Пошук по сайту


Курсова робота

Курсова робота

Сторінка1/2
  1   2

http://antibotan.com/ - Всеукраїнський студентський архів

Анотація

Горох Б.

“Оптимальне кодування. Код Шеннона-Фано”. Курсова робота. – НУ “Львівська політехніка”, каф.: ПЗ, дисципліна: “Методи та засоби комп`ютерних інформаційних технологій”, 2007.

Курсова робота складається з 32 сторінок, 5 таблиць і 8 рисунків.

В даній курсовій роботі спроектовано та розроблено програму, яка реалізовує кодування текстової інформації методом Шеннона-Фоно.

Програмний продукт надає можливості користувачу кодувати текст введений у вікні програми або відкритий з текстового файлу. Розкодовувати закодований текст та переглядати його, зберігати закодований текст у файл.

Є зручним та ефективним у використанні.

Зміст

Технічне завданя

Запис у файл реалізований за допомогою стандартної процедури SetLength, що встановлює довжину NewLength змінни S типу рядка або динамічного масиву. Та, процедури GetByte. Наведена нижче процедура реалізує перекодування бітів у байти, запис байтів у масив aFileArray та запис їх в файл з розширенням BYT. 23

procedure TForm1.Button7Click(Sender: TObject); 23

var 23

i:integer; 23

s:string; 23

l:integer; 24

begin 24

//--------------------------------- 24

s:=edit3.Text; 24

if (l mod 8)<>0 then 24

for i:=1 to 8-(l mod 8) do 24

s:=s+'0'; 24

l:=Length(s); 24

SetLength(aFileArray,0); 24

SetLength(aFileArray,l div 8); 24

for i:=0 to High(aFileArray) do 24

begin 24

aFileArray[i]:=GetByte(Copy(s,1+8*i,8)); 24

end; 24

//запис у файл 24

if SaveDialog1.Execute then aSaveFile(SaveDialog1.FileName); 24

end; 24

end. 24

3.5 Розробка інтерфейсу 24

Вступ

Фундаментальне поняття теорії інформації – ентропія, яку можна розглядати як міру кількості інформації в повідомленні. Під вартістю мається на увазі середня довжина кодового слова (в бітах) на один символ вихідного тексту. Надлишковість кодування дорівнює різниці між вартістю кодування та ентропією вихідного повідомлення з розрахунку на один символ. Надлишковість також можна розглядати як відношення кількості надлишкових символів до кількості корисних: за таких визначень очевидно, що надлишковість завжди є невід’ємною. Ефективний алгоритм стискання має мінімізувати надлишковість (в ідеальному випадку – звести до нуля). Фундаментальна теорема Шеннона про кодування джерел стверджує, що вартість кодування завжди не менша, ніж ентропія джерела, хоча й може бути як завгодно близька до неї. Це твердження встановлює теоретичні границі стискання даних.

1. Огляд методів оптимального кодування

Кодування (encoding) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.

Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена.

Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена.
1.1. Кодування Хаффмена

Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ.

Нехай вхідний алфавіт складається з чотирьох символів: a, b, c, d, частоти яких відповідно дорівнюють 1/2, 1/4, 1/8, 1/8.

Кодування Хаффмена для цього алфавіта подається таблицею 1.

Символ

Частота

Вхідне кодування

Вихідне кодування

A

1/2

00

0

B

1/4

01

10

C

1/8

10

110

D

1/8

11

111

Таблиця 1.1. Кодування Хаффмена



Рисунок 1.1. Дерево Хаффмена.

Наприклад, кодом ланцюжка abaaacb, поданого на вході як

00 01 00 00 00 10 01

буде

0 10 0 0 0 110 10

(проміжки додано для зручності читання). Отже, 14 біт на вході дали 11 біт на виході – стискання очевидне! На мал. 1 подано двійкове дерево Хаффмена для наведеного коду.

При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці.

Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).

Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.

Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2!

Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду “ab”, “abc”,..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам’яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання).

Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно.

1.2. Кодування Шенона-Фано

Кодування Шеннона-Фано є|з'являється| одним з найперших алгоритмів стиснення|стиснення||. Даний метод стиснення|стиснення| має велику схожість з|із| кодуванням Хаффмана, яке з'явилося|появлялося| на декілька років пізніше.

Алгоритм Шеннона-Фано використовує надмірність повідомлення, увязнену в неоднорідному розподілі частот символів його (первинного) алфавіту, тобто замінює коди частіших символів короткими двійковими послідовностями, а коди рідших символів - довшими двійковими послідовностями. Коди Шеннона-Фано префіксні, тобто, ніяке кодове слово не є префіксом будь-якого іншого. Ця властивість дозволяє однозначно декодувати будь-яку послідовність кодових слів. Алгоритм був незалежно один від одного розроблений Шеноном (публікація "Математична теорія зв'язку", 1948 рік) і, пізніше, Фано (опубліковано як технічний звіт).

Таким чином, алгоритм ґрунтується на кодах змінної довжини. Для того, щоб декомпресор згодом зміг розкодувати стислу послідовність, коди Шеннона-Фано повинні володіти унікальністю, тобто|цебто|, не дивлячись на їх змінну довжину, кожен код унікально визначає один закодований символ і не є|з'являється| префіксом будь-якої іншого коду.

Код Шеннона-фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає Кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковою сумарною вірогідністю. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковою сумарною вірогідністю. Їм відповідають вершини третього рівня. Якщо підмножину містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Так само поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0, як в разі коду Хаффмана. При побудові коду Шеннона-Фано розбиття безлічі елементів може бути проведене, взагалі кажучи, декількома способами. Вибір розбиття на рівні n може погіршити варіанти розбиття на наступному рівні (n+1) і привести до неоптимальності коду в цілому. Іншими словами, оптимальна поведінка на кожному кроці шляху ще не гарантує оптимальності всієї сукупності дій. Тому код Шеннона-фано не є оптимальним в загальному сенсі, хоча і дає оптимальні результати при деяких розподілах вірогідності. Для одного і того ж розподілу вірогідності можна побудувати, взагалі кажучи, декілька кодів Шеннона-Фано, і всі вони можуть дати різні результати. Якщо побудувати всі можливі коди Шеннона-Фано для даного розподілу вірогідності, то серед них знаходитимуться і всі коди Хаффмана, тобто оптимальні коди.

Приклад кодового дерева.

Початкові символи: A (частота тієї, що зустрічається 50), B (частота тієї, що зустрічається 39), C (частота тієї, що зустрічається 18), D (частота тієї, що зустрічається 49), E (частота тієї, що зустрічається 35), F (частота тієї, що зустрічається 24).



Рисунок 1.2.1 Дерева. Розподіл кодів.

Отриманий код: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.

Дерева і коди діляться на префіксні і непрефіксні:

В префіксних кодах повідомлення відповідають тільки кінцевим вершинам дерева.

Для непрефісних кодів повідомлення можуть розташовуватись в проміжних вузлах.

Префіксні коди можна розтиснути, непрефіксні неможливо однозначно розтиснути.

Кодування Шеннона-фано є достатньо старим методом стискування, і на сьогоднішній день воно не представляє особливого практичного інтересу. В більшості випадків, довжина стислої послідовності, по даному методу, дорівнює довжині стислої послідовності з використанням кодування Хаффмана. Але на деяких послідовностях все ж формуються неоптимальні коди Шеннона-фано, тому стискування методом Хаффмана прийнято вважати за ефективніше.

Для прикладу,|зразка|,,,,,,….,…жждлррролрлррлорл,,. розгледимо|розглядатимемо| послідовність з|із| таким змістом|вмістом| символів: 'a'| - 14, 'b'| - 7, 'c'| - 5, 'd'| - 5, 'e'| - 4. Метод Хаффмана стискує|стискає| її до 77 біт, а ось|от| Шеннона-Фано до 79 біт.

Таблиця 1.2.1 Порівняння коду Шеннона-Фано, Хафмена

Символ

код Хаффмана

код Шеннона-фано

а

0

00

b

111

01

з

101

10

d

110

110

e

100

111

До речі, в одному джерелі (не указуватиму якому), цю послідовність стискували методом Шеннона-Фано до 84 біт, а методом Хаффмана до тих же 77. Такі відмінності| в ступені стискування виникають із-за нестрогого визначення способу ділення символів на групи.

Як же ми ділили на групи? Досить просто: імовірність першої групи (p1) і другої (p2) дорівнює нулю;

p1 <= p2 ?

- так: додати в першу групу символ з початку таблиці;

- ні: додати в другу групу символ з кінця таблиці;

Якщо всі символи розділені на групи, то завершити алгоритм, інакше перейти до кроку 2.

1.3 Алгоритм Шеннона-Фано

  • Символи первинного алфавіту m1 виписують в порядку спадання вірогідності.

  • Символи отриманого алфавіту ділять на дві частини, сумарна вірогідність символів яких максимально близька один одному.

  • У префіксному коді для першої частки алфавіту привласнюється двійкова цифра "0", другій частці - "1".

  • Отримані частки рекурсивно ділятся і їх часткам призначаються відповідні двійкові цифри в префіксному коді.

  • Коли розмір підалфавіту стає рівний нулю або одиниці, то подальшого подовження префікснго коду для відповідаючого йому символу первинного алфавіту не відбувається, таким чином, алгоритм привласнює різним символам префіксні коди різної довжини. На кроці ділення алфавіту існує неоднозначність, оскільки різниця сумарної вірогідності p0, p1 може бути однакова для двох варіантів розділення (враховуючи, що всі символи первинного алфавіту мають вірогідність, більшу нуля).

Розглянемо|розглядатимемо| алгоритм обчислення|підрахунку| коду Шеннона-Фано детальніше: (для наочності|наглядний| візьмемо як приклад|зразок| послідовність 'Aa| bbb| cccc| ddddd|'). Для обчислення|підрахунку| коду, необхідно створити таблицю унікальних символів повідомлення(ь) і їх вірогідності|ймовірності| p(с|із|(i)), і відсортувати її в порядку спадання.

Таб.1.3.1 Ймовірності символів

с|із|(i)

p(с|із|(i))

d|із|

5 / 17

з

4 / 17

space

3 / 17

b

3 / 17

а

2 / 17

Далі, таблиця символів ділиться на дві групи так, щоб кожна з груп мала приблизно однакову частоту по сумі символів. Першій групі встановлюється початок коду в '0'|, другий в '1'|. Для обчислення|підрахунку| наступних|таких| біт кодів символів, дана процедура повторюється рекурсивно для кожної групи, в якій більше одного символу. Таким чином для нашого випадку отримуємо|одержуємо| наступні|слідуючі| коди символів:

Таб.1.3.2 Коди символів

Символ

Код

d|із|

00

з

01

space

10

b

110

а

111

Довжина коду s(i) в отриманій|одержувати| таблиці рівна int|(-lg| p(с|із|(i))), якщо символи| вдалося розділити на групи з|із| однаковою частотою, інакше, довжина коду рівна int|(-lg| p(с|із|(i)))+ 1.

int|(-lg| p(с|із|(i))) <= s(i) <= int|(-lg| p(с|із|(i)))+ 1

Використовуючи отриману|одержувати| таблицю кодів, кодуємо вхідний потік - замінюємо кожен символ відповідним кодом. Природно для розтиснення отриманої|одержувати| послідовності, дану таблицю необхідно зберігати разом із стиснутим потоком, що є|з'являється| одним з недоліків|нестач| даного методу. У стиснутому вигляді|виді|, наша послідовність набирає вигляду:

111111101101101101001010101100000000000

завдовжки в 39 біт. Враховуючи, що оригінал мав довжину рівну 136 біт, отримуємо|одержуємо| коефіцієнт стискування|стиснення| ~28% - не так вже і погано.

Дивлячись на отриману|одержувати| послідовність, виникає питання: " А як же тепер це розтискати? ". Ми не можемо, як в разі|у разі| кодування, замінювати кожні 8 біт вхідного потоку, кодом змінної довжини. При розтиснені нам необхідно все зробити навпаки - замінити код змінної довжини символом завдовжки 8 біт. В даному випадку, краще всього використовувати бінарне дерево, листям якого будуть|з'являтимуться| символи (аналог дерева Хаффмана).



Рис. 1.3.1. Дерева. Префіксні входи

Недоліком такого методу кодування є крихкість коду – його нестійкість до спотворень, завад.

2. Постановка задачі та обґрунтування вибраного напряму проектування

Оскільки дискретне представлення інформації має в цілому більш загальний характер широко застосовуються дискретні способи уявлення. Застосовується цифровий код заснований на позиційній системі числення з підставою 10, 8, 16, 2. Двійкова система застосовується оскільки вимагає найменшої кількості розрядів. Прикладом дискретних пристроїв являются нейрони головного мозку.

Вибір оптимальної системи числення.

Для оптимального запису даних необхідно, щоб запис досягався найменшою кількістю символів при найменшій же кількості розрядів. Ці умови є суперечливими. Припустимо, що оптимальною системою є та, яка дозволяє обійтися найменшою кількістю апаратури. Кількість апаратури слід покласти пропорційним створення числа символів s на число розрядів N. Найбільше число символів, яке можна записати

M= sN - 1 (K.1)

Наприклад в десятковій системі за допомогою трьох розрядів запишемо:

M= 103-1=999

З (K.1) знайдемо

N= ln(M+1) /ln s

Кількість апаратури пропорційна

Ns = s ln(M+1)/ ln s

Умовою мінімуму аппартури є рівність нулю похідної правої частки даного рівняння, отже

Lns -1=0, отже

S=e (2.71)

Відзначимо, що основа системи числення має бути цілим числом.

Вивід

Якнайкращої по критерію мінімуму апаратури є трійкова система числення.

Проте з ряду причин технічного характеру застосовується двійкова система, яка дає декілька гірший результат.

Двійкова система добре узгоджується з двійковою логікою і двійковим кодуванням.

Аналогії з живої природи. Мозок і його робота. Нервова система і мозок складаються з нейронів. Будова нейрона наступна - декілька дендридів по яких приймається інформація і єдиний аксон по якому імпульс передається наступним нейронам при збудженні останнього через синапси. Враховуючи, що на силу імпульсу впливає аксон (який з'єднується з нейроном через синапси) можна сказати, що в простому випадку система зможе приймати три стани - немає сигналу, гальмування і збудження (сигнал видається наступним нейронам).

Підстава системи числення або логарифма при обчисленні обємів інформації визначає одиницю виміру інформації і ентропії.

Двійкова система- біт

Натуральна (е=2,718) - ніт (1 ніт= 1,44269 біт)

10 - діт (1 дит= 3, 32193 біт)

Ефективне кодування. Вибір оптимального коду.

Простий варіант - застосування рівномірного коду, в якому кожен символ кодується одинковим числом розрядів.

Приклад

A - 00, B - 01, C- 10, D-11.

Середня довжина повідомлення залежить від вірогідності появи символів коду.

S = S Pi Li

Припустим

Pa=1/2

Pb=1/4

Pc=1/8

Pd=1/8

При рівній довжині коду (2) - середня довжина повідомлення складе - 2

Закодуємо повідомлення інакше

A - 0, B - 10, C- 110, D-111 (Відзначимо, що повідомлення можна повністю відновити з його початкової форми).

Тоді

S= 1*1/2+2*1/4+3*1/8+3*1/8=1,75

Отже оптимальний код відповідає ентропії, розрахованої для вірогідності появи символів PI

Фрагмент коду приведений вище називається кодом Шеннона-Фано.

Таблиця 2.1 Код Шеннона-Фано

Розставимо символи в порядку убування вірогідності










Підсумок

A

Pa=1/2

0







0

B

Pb=1/4

1

0




10

C

Pc=1/8

1

1

0

110

D

Pd=1/8

1

1

1

111


Під час виконання курсової роботи було поставлено задачу програмно реалізувати алгоритм кодування Шеннона-Фано.

Даний програмний продукт повинен бути призначений для кодування тексту різного типу, та збереження його у зменшеному форматі. Програма повина працювати в віконному режимі. Інтерфейс повинен бути досить простий і легкий до розуміння та використання.

Вхідними даними повинен бути текст введений користувачем у відповідному вікні програми, або текстовий файл відкритий засобами програми.

Вихідною повина бути інформація представлена після певного кроку виконання алгоритму у відповідному елементі програми а саме:

1. Вірогідності появи символів;

2. Впорядковані символи за спаданням вірогідності;

3. Алфавіт кодів;

4. Закодований текст.

Програма повинна працювати з текстовими файлами, які знаходяться в будь-якій директорії.

Також програма повинна виконувати збереження закодованого тексту в файл з розширенням byt та розкодованого тексту в файл з розширенням txt.
3. Програмна реалізація

Курсовий проект розроблявся в середовищі Delphi 7. Це дозволило швидко реалізувати зручний користувацький інтерфейс, опрацювання відкривання та закривання файлів. Для роботи з відкриттям та збереженням файлів Delphi надає діалогові компоненти:

TOpenDialog відображає модальні діалогові вікна Windows для відкриття (збереження) файлів. Компоненти TOpenDialog і TSaveDialog працюють з файлами будь-якого типу.

Відкриття відповідного діалогу здійснюється методом Execute. Якщо в діалозі користувач натискуватиме кнопку Відкрити (Зберегти), діалог закривається, метод Execute повертає true і вибраний файл відображається у властивості компоненти-діалогу FileName. Якщо ж користувач відмовився від діалогу (натиснув кнопку Відміна або клавішу Esc), то метод Execute повертає false. Значення властивості FileName можна задати і перед зверненням до діалогу. Тоді воно з'явиться в діалозі як значення за замовчуванням у вікні Ім'я файла. Таким чином виконання команди Зберегти як ..., по якій у файлі з вибраним користувачем ім'ям треба зберегти текст вікна редагування Memo5, може мати вигляд:

if savedialog1.Execute then

memo5.Lines.SaveToFile(savedialog1.FileName);

Також інтегроване середовище програмування Delphi 7 надає Багато процедур і функцій обробки файлів, на які вказують дескриптори.

FileWrite(Handle: Integer; const Buffer; Count: Integer): Integer

Записує у файл, вказаний своїм дескриптором Handle з Buffer число байтів Count. Повертає число дійсно записаних байтів.

FileRead(Handle: Integer; var Buffer; Count: Integer): Integer

Читає з файлу, вказаного своїм дескриптором Handle (FileCreate і FileOpen) в Buffer число байтів Count. Повертає число дійсно прочитаних байтів.

3.1 Програмна реалізація кодування методом Шеннона-Фано

3.1.1 Вибір та обрахунок ймовірність появи символів в тексті

В даному розділі описується реалізація одиного з кроків алгоритму Шеннона-Фано, а саме, обрахунок ймовірності появи символів у вибраному тексті. Для цього потрібно, спочатку, визначити загальну кількість символів у тексті. Далі, визначити кількості появ кожного символу, та поділити кожне з цих значень на кількість символів у тексті. Для реалізації даного кроку був використаний цикл та стандартні функції length та copy:

begin

s:=Edit2.Text;

ds:=length(s);

for i:=1 to ds do

begin

s2:=Edit1.Text;

search:=''+s[i];

kilk:=0;

while (pos(search,s2) <> 0) do

begin

kilk:=kilk+1;

s2:=copy(s2, pos(search,s2)+1,length(s2)- pos(search,s2));

end;//while

imov[i]:=kilk/length(Edit1.Text);

Memo1.Lines.Add(s[i]+' '+IntToStr(kilk)+' '+FloatToStr(imov[i]));

end;//i

end;

3.1.2 Впорядкування ймовірностей

Фрагмент коду описаний нижче призначений для впорядкування ймовірностей появи символів у слові за спаданням. Для цього виконується порівняння кожної ймовірності з наступною і більша з них переміщується на початок:

for j:=1 to ds-1 do

for i:=1 to ds-j do

if imov[i] < imov[i+1] then

begin

temp:=imov[i];

imov[i]:=imov[i+1];

imov[i+1]:=temp;
temp2:=s2[i];

s2[i]:=s2[i+1];

s2[i+1]:=temp2;

end;

В циклі формується масив ймовірностей і виводить у Мемо:

for i:=1 to ds do

begin

Memo2.Lines.Add(s2[i]+' '+FloatToStr(imov[i]));

end;
3.1.3 Поділ множини повідомлень на дві частини

Поділ множини повідомленнь здійснюєтся наступним чином: береться перша (найбільша) вірогідність і порівнюється із сумою всіх решта, що під нею. Якщо вона менша, то до неї додається наступна, і ця вірогідність віднімається від «нижньої» суми результати знову порівнюються. Порівнюється різниця між цими сумами.

for i:=2 to ds do

begin

sum2:=sum2+imov[i];

end;

min:=abs(sum1-sum2);

for i:=2 to ds do

begin

sum1:=sum1+imov[i];

sum2:=sum2-imov[i];

if (abs(sum1-sum2) < min)
При найменшій різниці ставить умовна риска – змінній присвоюється номер ймовірності, після якої слідує риска:

then

begin

min:=abs(sum1-sum2);

riska:=i;

end;
3.1.4 Присвоєння значення символу

Присвоєння реалізуєтся так :

Всі значення символів зберігаються у масиві, який у циклі виводиться як результат у Мемо, до нього дописується масив кодів, який повертає вище описана функція:

for i:=1 to length(Edit2.Text) do

begin

edit3.Text:=edit3.Text+codes2[i];

memo4.Lines.add(codes[i]);

end;
3.1.5 Визначення значення наступного розряду коду

Визначення реалізує функція: getRiska, яка визначає кожне наступне значення відповідним кроком циклу. Вона отримує як параметри номер першої ймовірності та довжину алфавіту повідомлень:

for i:=1 to length(Edit2.Text) do

begin

codes2[i]:=codes[i];

codes[i]:=letters[i]+' = ';

end;

Label2.Caption:=intTostr(getRiska(1,length(Edit2.Text)));
3.3 Процедура декодування методом Шеннона-Фано

Процедура декодування бере кожен код з масиву кодів і за допомогою функції pos шукає відповідний йому символ. Якщо відповідність знайдена, то за допомогою функції copy формується результат (рядок символів що відповідають кодам)

procedure TForm1.Button2Click(Sender: TObject);

var

s,search:string;

i:word;

ls,ll: integer;

begin

Edit4.Text:='';

s:= Edit3.Text;

ls:= length(s) ;
while length(s) > 0 do

begin

ll:=length(sortedSymbols);

for i:=1 to length(sortedSymbols) do

begin

search:=codes[i];

if pos(search,s)=1 then

begin

Edit4.Text:=Edit4.Text+sortedSymbols[i];

s:=copy(s, pos(search,s)+length(codes[i]),length(s)-length(codes[i]));

break;

end;

end;

end;

Memo5.Text:=Edit4.Text;

end;
3.4 Реалізація запису у файл
  1   2

поділитися в соціальних мережах



Схожі:

Курсова робота
Курсова робота з дисципліни „Маркетинг”/ О. В. Полюхович, Рівне: нувгп, 2012, – 44 с

Курсова робота з дисципліни «Статистика» на тему: «Статистичне вивчення...
Курсова робота відповідає вимогам діючої нормативної документації України та умовам ects/кмсонп

Курсова робота з дисципліни «Статистика» на тему: «Статистика продукції промисловості»
Курсова робота відповідає вимогам діючої нормативної документації України та умовам ects/кмсонп

4. Курсова робота має характер цільної завершеної роботи як стосовно...
Курсова робота є до курсовим завданням І подається куратору курсі в на 3-й день перебування на курсах

” Навчально-дослідна робота (курсова робота) студента з „Економіки...
...

Курсова робота
Мікропрограма

Курсова робота
Вступ

Курсова робота
Вступ

Курсова робота на тему: “Міжнародні банківські розрахунки
Вступ

Курсова робота на тему: «Епічний театр Бертольда Брехта»
Висновки



База даних захищена авторським правом © 2017
звернутися до адміністрації

l.lekciya.com.ua
Головна сторінка