Методи стискання цифрової інформації Метод Лавинский

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти і науки України
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсового проекту
на тему: "Методи стискання цифрової інформації. Метод Лавинский"
за курсом "Кодування та захист
інформації "
2004

Зміст


Введення
1. Постановка завдання
2. Огляд існуючих методів рішення задачі
2.1 Стиснення і кодування інформації в інформаційно обчислювальних комплексах (ІВК)
2.2 Стиснення з відновленням
2.3 Методи стискання цифрової інформації з повторюваними фрагментами
3. Вибір і обгрунтування рішення задачі
4. Теоретичне обгрунтування методу Лавинский
5. Програмне забезпечення та інформаційний вибір методу
Висновок
Бібліографічний список
Додаток А
Додаток Б

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

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

2. Огляд існуючих методів рішення задачі
2.1 Стиснення і кодування інформації в інформаційно обчислювальних комплексах (ІВК)
ІВК - це набір, що складається з одного або декількох ЕОМ, забезпечених пристроями зберігання, введення виведення і передачі інформації. ІВК має окремі пристрої, рознесені між собою.
Інформаційна мережа являє собою набір ІВК, з'єднаних між собою каналами передачі інформації (канали можуть бути будь-якої протяжності). Для того, щоб мережа могла функціонувати, вона забезпечується набором протоколів і інтерфейсів.
Протокол - деяке безліч інформаційних функцій і алгоритмів обробки інформації, які прийняті в тій чи іншій мережі.
Інтерфейс - деяке з'єднання або канал між окремими функціональними частинами мережі. Інтерфейси бувають фізичні і програмні.
Фізичний інтерфейс - набір шин, для передачі сигналів, та електричних пристроїв для управління проходження сигналів по цим шинам. Більшість фізичних інтерфейсів - стики.
Програмний інтерфейс - частина програмного забезпечення мережі, що відповідає за передачу інформації від вузла до вузла.
Мережі можуть бути гомогенними і гетерогенними (однорідними і різнорідними).
У гомогенних мережах використовуються однотипні ЕОМ і однотипні програмне забезпечення.
У гетерогенних мережах протоколи, крім усього іншого, узгодять різнорідне програмне забезпечення, а інтерфейси узгодять фізичні пороги сигналів.
Всі універсальні мережі є гомогеннимі.Сеть найчастіше є відкритою системою.
Відкритої називається така система, яка може взаємодіяти з іншими системами. Для того, щоб відкрита система нормально функціонувала вона повинна забезпечувати сім рівнів цього функціонування:
прикладної
представницький
сеансовий
транспортний
мережевий
канальний
фізичний
Прикладний рівень функціонування передбачає уніфікацію і

стандартизацію керуючих сигналів, формати інформаційних кадрів, методів кодування та захисту від помилок і основні службові посилки.
Ф1 та Ф2 - прапори;
А - адреса;
З Про - захист від помилок.
Представницький рівень уніфікує форму подання інформації, тобто тип сигналів, вид кодів, способи захисту від помилок і правила семіотики (науки про знаки) для вибраної знакової системи.
Сеансовий рівень уніфікує тривалість сеансів зв'язку між вузлами мережі, службову інформацію для виклику або організації таких сеансів, спосіб стиковки між функціональними частинами при сеансі зв'язку.
Транспортний рівень уніфікує власне передачу інформації, тобто її швидкість або час, спосіб передачі (паралельно, послідовно або змішано) інформації та види модемів та апаратури передачі даних.
Мережевий рівень уніфікує (стандартизує) проходження сигналів по чергах, вигляд цих черг, спосіб обслуговування, різновиди персонального захисту та доступу (ключі, паролі, шифри).
Канальний рівень уніфікує проходження сигналів по каналу з допомогою уніфікації ініціалізації, синхронізації та апаратури захисту від помилок.
Фізичний рівень проводить уніфікацію фізичних сигналів за рівнем (амплітуді), частоті, фазі і по вигляду модуляції сигналів.
У відкритих мережах, на увазі величезних обсягів проходить інформації, проводиться стиснення інформації. Існує стиснення без відновлення і з відновленням. Стиснення без відновлення припускає, що передається алфавітно-цифрова інформація, яка тим або іншим способом зменшується в об'ємі і на приймальній стороні приймається стислий обсяг. А при стисненні з відновленням приймач отримує початковий текст, за умови, що передавався стислий текст. У загальному випадку, стиснення (компресія) даних являє собою процес виділення з вихідного інформаційного масиву його інформативної частини шляхом відкидання деяких символів, які несуть мінімальне число цієї інформації. Стиснення проводиться до тих пір, поки інформативність зберігається. Найпростіший спосіб стиснення без відновлення для текстової інформації на природній мові, припускає наявність словника заборон, який підтримується мережею і доводиться до всіх абонентів. У нього входять одне, двох і трибуквені слова з мінімальною інформативністю, які з тексту виключаються. З тексту, починаючи від кінця слова до початку, прибирають всі голосні і частина згодних до наявності ще в слові необхідного сенсу. Перші три приголосні несуть 84% інформації.
Якщо інформація представлена ​​в цифровому вигляді, то в цьому випадку задають довжину блоку, до якого необхідно її стиснути.
Весь текст б'ється на блоки заданої довжини або меншою і потім проводиться або складання їх за модулем два, або двійкове додавання і передається їх сума.

Якщо інформація не цифрова, а текстова, то можна використати той же метод, якщо кожну букву закодувати деяким кодом рівномірної довжини.
Å
n £ 9

У тому випадку, якщо довжина блоку, що кодує букву менше, ніж необхідна довжина блоку для передачі, складання проводиться при ступінчастому зсуві однієї букви щодо іншої на одну позицію вліво, починаючи від першої літери слова до останньої.
2.2 Стиснення з відновленням
Методи стиснення з відновленням повинні забезпечити перехід до вихідного повідомлення при заданому КСЖ.
n1 - число символів у вихідному повідомленні


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

2.3 Методи стискання цифрової інформації з повторюваними фрагментами

Передбачається, що інформація записується у файли. Перша частина застосовна для тих інформаційних масивів, в яких повторюються фрагменти стоять на початку рядка. У цьому випадку використовується символ пропуску r, весь масив передається одним рядком.
123456r7r41r2
Відновлення починається від кінця до початку, при відомій кількості символів в рядку. Запис кожного рядка виробляється до символу пропуску.

Далі зверху вниз записуємо символи попереднього рядка.
Другий спосіб використовується для тих масивів, в яких повтори не тільки на початку рядка: використовується символ r і символ кінця рядка k.


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



Відновлення починають з першої вихідної рядки, де кількість пропусків визначається попередньої рядком.
Якщо інформація анкетного типу, записана в алфавітно-цифровій формі, то можна використовувати замість частини повторюваного тексту два значки (символу). Один з символ повтору, а другий - скільки букв пропущено при повторі.
Електронне дистанційне реле РВ - 10
Електронне дистанційне реле РВ - 11
Електронне дистанційне реле РВ - 10
* 32 1


2.4 Зонне стиск
Метод зонного стиснення використовують для текстових масивів з урахуванням символів природного алфавіту і знаків пунктуації.
28 = 256
запропоновано використовувати чотири біта (полубайта) для запису кожної букви, тим самим створюючи деякий алфавіт з шістнадцяти букв, де кожна клітинка дає нам m = 24 = 16
162 = 256
Ми наші шістнадцять літер ділимо на деяку кількість зон:

0
0000
4
0100
8
1000
1
0001
5
0101
9
1001
2
0010
6
0110
A
1100
3
0011
7
0111
B
1011
C
1100
D
1101
E
1110
F
1110
Для російського алфавіту досить 13 літер, розподілених по трьох зонах.
0 ... С - імена літер
D ... F - імена зон
З урахуванням ймовірності появи літер один з одним в тексті, таблиця для російського алфавіту виглядає наступним чином:
D
E
F
0
Space
З
Ц
1
Про
У
Ж
2
Е
Д
Х
3
А
Я
Ч
4
Р
Ь
Е
5
П
Ф
Ю
6
Т
И
,
7
Н
Щ
.
8
У
Ш
;
9
І
Б
:
A
З
Г
!
B
М
До
?
C
Л
Й
-
Стиснення визначається знаходженням літер в одній або в сусідніх зонах. І вірогідність знаходження букви де-небудь по відношенню до іншої букві:
а - ймовірність знаходження букви в зоні D

б - ймовірність знаходження букви в зоні E
в - ймовірність знаходження букви в зоні F
Кожна літера записується двома символами:
номер зони
номер літери
якщо поруч стоять букви потрапляють в одну зону, то номер зони пишеться тільки один раз, а букви чергуємо.


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

3. Вибір і обгрунтування рішення задачі
4. Теоретичне обгрунтування методу Лавинский
Даний метод передбачає стиск послідовності чисел шляхом розбиття послідовності на рівномірні інтервали і відшукання числа не в його натуральному вигляді шляхом перебору всіх підряд, а за допомогою порядкового номера відліку від найближчої кордону.
Сам метод полягає в наступному. Нехай маємо деяку кількість чисел М і максимальне по довжині число L. Очевидно, що для зберігання в натуральному вигляді цих чисел необхідно наступне кількість осередків
Q = M * log 2 L (1)
Лавинский запропонував безліч М розбити на N інтервалів. Інтервали між собою рівні і тоді очевидно, що для зберігання самих чисел необхідний наступний обсяг пам'яті
Q '= M * log 2 (L / N) (2)
І нам необхідно зберігати інформацію про ці самі межах
Q "= (M - 1) * log 2 (N - 1) (3)
У цілому обсяг пам'яті необхідний для самих чисел і пам'яті буде наступним
Q = Q '+ Q "(4)

Взявши похідну з (4), для знаходження оптимального розбиття послідовності і прирівнявши її нулю, отримаємо
N ОПТ = М / ln M (5)
Формула (5) визначає оптимальну кількість інтервалів. Для визначення величини самого інтервалу ми всю кількість можливих варіантів відносимо до кількості самого інтервалу, тобто для визначення кількості символів в інтервалі використовуємо таку формулу
C = 2 [log2 N] / N (6)
Для знаходження самого інтервалу (номер кордону) використовуємо наступне відношення
К = Х / С (7),
де Х - шукане число в натуральному вигляді.
Після цього саме число записується, як порядковий відлік цього кордону і визначає економію пам'яті як
DQ = QІСХ - qопт (8)
Нехай інтервал 128, Х = 200, тоді К = 1.56. До лежить 2> K> 1, значить код числа складе 200 - 127 = 73.

5 П рограммная реалізація
Для розробки програми була вибрана мова програмування високого рівня Delphi 5.0 (Object Pascal).
Він дуже повно виражає ідеї структурного програмування. Це проявляється в тому, що Delphi може успішно використовуватися для запису програм на різних рівнях її деталізації, не вдаючись до допомоги блок-схем або спеціальної мови проектування програм. Засоби мови Delphi дозволяють здійснювати достатній контроль правильності використання даних різних типів і програмних об'єктів як на етапі трансляції, так і на етапі її виконання.
Delphi дозволяє без особливих труднощів реалізувати зручний користувальницький інтерфейс, не пребегая до написання низькорівневого коду.
У програмі є також можливість вважати дані для кодування з файлу.

Висновок
У ході виконання курсової роботи були закріплені знання, отримані в ході вивчення дисципліни «Кодування та захист інформації». Робота виконана у відповідності з постановкою завдання на курсове проектування.
Для перевірки працездатності програми і правильності обробки вхідних даних розроблено тестовий приклад. Тестування програми підтвердило, що програма правильно виконала обробку даних і видає вірні результати.

Бібліографічний список
Конспект лекцій з дисципліни "Кодування та захист інформації".
Березюк Н. Т., Андрющенко А. Г., Мощинський С. С. та ін Кодування інформації - Харків: Вища школа, 1978. - 252 с.
Кузьмін І. В., Кедрус В. А. Основи теорії інформації та кодування. - Київ: Вища школа, 1977. - 280 с.
Цимбал В. П. Теорія інформації та кодування. Київ, "Вища школа", 1997, 288 с.

Додаток А

uses
Forms,
Kizi in 'Kizi.pas' { Main };
{$ R *. res}
begin
Application.Initialize;
Application.CreateForm (TMain, Main );
Application.Run;
end.
unit Kizi;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, math;
type
TMain = class (TForm)
Button1: TButton;
Button2: TButton;
Button3: TButton;
fOpen: TOpenDialog;
fSave: TSaveDialog;
procedure Button3Click (Sender: TObject);
procedure Button1Click (Sender: TObject);
procedure Button2Click (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
var
Main : TMain;
f, f1: textfile;
i1: integer; / / лічильник елементів (чисел) у файлі
massivelementov: array [0 .. 24] of longint; / / стискається масив
massivelementov1: array [0 .. 3,0 .. 4] of longint; / / робочий масив розбитий на інтервали
kolelementovfila: real; / / кількість елементів М
maxchislo: integer; / / Максимальне число з М
chisloposled: integer; / / Кількість елементів в інтервалі
Interval: integer; / / кількість інтервалів
kolmetok: integer; / / колічесьво міток
k: real; / / прапор опред мітки
polovina: real; / / половина інтервалу
nomer: integer; / / порядковий номер масиву
granica: array of integer; / / порядковий номер кордону від нуля
mm: integer;
implementation
{$ R *. dfm}
function DecToBin (dec: integer): string;
var
bin: string;
i: integer;
begin
bin :='';
for i: = 1 to 8 do
begin
bin: = inttostr (dec mod 2) + bin;
dec: = dec div 2;
end;
DecToBin: = bin;
end;
function Bin24ToDec24 (bin: string): integer;
var
i: integer;
dec: integer;
begin
if strlen (pchar (bin)) <24 then
for i: = strlen (pchar (bin)) +1 to 24 do
bin: = '0 '+ bin;
dec: = 0;
for i: = 0 to 23 do
dec: = dec + trunc (strtoint (copy (bin ,24-i, 1)) * intpower (2, i));
Bin24ToDec24: = dec;
end;
function Dec24ToBin24 (dec: integer): string;
var
bin: string;
i: integer;
begin
bin :='';
for i: = 1 to 24 do
begin
bin: = inttostr (dec mod 2) + bin;
dec: = dec div 2;
end;
Dec24ToBin24: = bin;
end;
procedure TMain.Button3Click (Sender: TObject);
begin
Main.close;
end;
procedure TMain.Button1Click (Sender: TObject);
var
c: char;
g, i, j: integer;
fileperem: array [0 .. 9999] of char;
fileperem1: array [0 .. 9999] of string;
flag1: integer; / / лічильник символів у файлі
flag2: integer; / / лічильник елементів масиву fileperem1
flag3: integer; / / прапор змісту букви в фмйле
flag4: integer; / / прапор виходу з блоку читання з файлу
flag5: integer; / / умова збільшення прапора flag2
metca: integer; / / для визначення значення інтервла
outBuf: array [1 .. 3] of Char;
outf: file of char;
outpos: integer;
outcomb: string;
tmp: char;
k: integer;
begin
/ / Читання з файлу
//---------------------------------------
fopen.Filter: = 'Текстові файли | *. txt';
fsave.Filter: = 'заархівовані файли | *. arhi';
While flag4 <> 1 do
begin
i: = 0;
flag4: = 1;
if fopen.Execute then
begin
flag3: = 0;
assignfile (f, fopen.filename);
reset (f);
for i: = 0 to 9999 do fileperem [i]: = '';
i: = 0;
while (not eof (f)) and (i <100000) do
begin
read (f, c);
if (c <> '') and ((c <0 ") or (c> '9 ')) and (c <>'-') and (c <>'+') and (c <> # 13) and
(C <> # 10) then
begin
if MessageDlg ('Фаил містить буквений символ. Вказати інший фаил?',
mtconfirmation, [mbYes, mbno], 0) = mryes
then flag3: = 1 else flag3: = 11;
i: = 1000000;
end else
begin
fileperem [i]: = c;
i: = i +1;
if i> 99999 then
begin
showmessage ('Фаил занадто великий');
flag3: = 1;
i: = 1000000;
end;
end;
end;
end;
if flag3 = 1 then
begin
flag3: = 12;
flag4: = 0;
end;
end;
//---------------------
/ / Забивання робочого масиву
//------------------------------
flag1: = 0;
flag2: = 0;
if (flag3 = 0) or (flag3 = 1) and (flag3 <> 11) then
begin
if flag3 <> 1 then
begin
while flag1 <= i do
begin
while (fileperem [flag1] <> # 13) and (fileperem [flag1] <> '') and
(Fileperem [flag1] <> # 10) do
begin
fileperem1 [flag2]: = fileperem1 [flag2] + fileperem [flag1];
flag1: = flag1 +1;
flag5: = 1;
end;
flag1: = flag1 +1;
if flag5 = 1 then
begin
flag2: = flag2 +1;
flag5: = 0;
end;
end;
kolelementovfila: = flag2;
{SetLength (massivelementov, trunc (kolelementovfila));
SetLength (massivelementov1, trunc (kolelementovfila));}
maxchislo: = strtoint (fileperem1 [0]);
for i: = 0 to trunc (kolelementovfila) -1 do
begin
massivelementov [i]: = strtoint (fileperem1 [i]);
if maxchislo <massivelementov [i] then maxchislo: = massivelementov [i];
end;
end;
end;
//---------------------------------
/ / Алгоритм кодування
//---------------------------------
/ / Визначення кількості інтервалів і числа символів в них
//---------------------------------
if (flag3 = 0) or (flag3 = 1) and (flag3 <> 11) then
begin
chisloposled: = {trunc (kolelementovfila / trunc (ln (kolelementovfila))) +1} 5;
Interval: = {trunc (kolelementovfila / chisloposled) +1} 5;
kolmetok: = trunc (Interval) -1;
SetLength (granica, kolmetok);
metca: = 0;
for i: = 0 to kolmetok-1 do
begin
granica [i]: = i;
end;
i: = 0;
j: = 0;
nomer: = 0;
/ / Кодування
while J <= kolmetok-1 do
begin
massivelementov1 [j, i]: = massivelementov [nomer]-trunc (granica [j]) * 150;
nomer: = nomer +1;
i: = i +1;
if i = chisloposled then
begin
{Nomer: = 0;}
J: = J +1;
i: = 0;
end;
end;
closefile (f);
if fsave.Execute then
begin
AssignFile (outf, fsave.filename + '. Arhi');
Rewrite (outf);
outpos: = 0;
for i: = 0 to kolmetok-1 do
for j: = 0 to Interval-1 do
begin
tmp: = chr (granica [i]);
write (outf, tmp);
inc (outpos);
seek (outf, outpos);
outcomb: = dec24tobin24 (massivelementov1 [i, j]);
for k: = 1 to 3 do
outbuf [k]: = chr (bin24todec24 (copy (outcomb, k * 8-7,8)));
for k: = 1 to 3 do
begin
write (outf, outbuf [k]);
inc (outpos);
seek (outf, outpos);
end;
end;
CloseFile (outf);
end;
end;
end;
procedure TMain.Button2Click (Sender: TObject);
var inf: file of char;
outf: textfile;
inbuf: array [1 .. 3] of char;
temp: string;
k: integer;
inpos: integer;
tmp: char;
massive, chislo, granica: integer;
begin
fopen.Filter: = 'заархівовані файли | *. arhi';
fsave.Filter: = 'Текстові файли | *. txt';
if fopen.execute and fsave.execute then
begin
AssignFile (inf, fopen.Filename);
Reset (inf);
inpos: = 0;
AssignFile (outf, fsave.Filename);
Rewrite (outf);
inpos: = 0;
while not (eof (inf)) do
begin
read (inf, tmp);
inc (inpos);
Seek (inf, inpos);
granica: = ord (tmp);
for k: = 1 to 3 do
begin
read (inf, inbuf [k]);
inc (inpos);
Seek (inf, inpos);
end;
temp :='';
for k: = 1 to 3 do
temp: = temp + dectobin (ord (inbuf [k]));
massive: = bin24todec24 (temp);
chislo: = massive + granica * 150;
write (outf, inttostr (chislo), '');
end;
closefile (outf);
closefile (inf);
end;
end;
end.

Додаток Б
Керівництво користувача
Для початку користувач повинен попередньо підготувати текстовий файл вихідних даних (*. txt), в якому повинен знаходитися масив чисел.
Після за пуску програми (KiZI.ехе) на екрані з'явиться панель на якій знаходиться три кнопки:
· Архівація
· Деархівація
· Вихід
При натисканні кнопки «Архівація» з'явиться вікно «Відкрити файл для архівації», де користувачеві запропоновано вибрати текстовий файл з вхідними даними, якщо користувачем у файл з вхідними даними буде записана інша символ крім числа, то програма видасть помилку: "Файл містить буквений символ. Вказати інший файл? »
· При натисканні кнопки «Yes» користувачу буде запропоновано вибрати інший файл;
· При натисканні кнопки «No» користувач буде повернений в початкове меню;
Якщо файл, вибраний користувачем містить коректні вхідні дані (числа), то програма запропонує користувачеві вікно "Зберегти заархівований файл», де користувачеві потрібно тільки вибрати папку куди файл потрібно зберегти і ввести ім'я файлу, розширення програма додасть сама (*. arhi). У цей файл програма запише заархівованих інформацію.
При натисканні кнопки «Деархівація» з'явиться вікно «Відкрити файл для архівації», де користувачеві запропоновано вибрати архівний файл, потім користувачеві програма запропонує вікно "Зберегти заархівований файл», де користувачеві потрібно вибрати тільки папку, куди потрібно зберегти файл і ввести ім'я файлу, розширення програма додасть сама (*. txt). У цей файл програма запише розархівований інформацію.
При натисканні кнопки «Вихід» програма закінчує свою роботу і відбувається вихід в операційну систему.
Програма проводить стиснення інформації приблизно на 14%.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
73.4кб. | скачати


Схожі роботи:
Методи стискання інформації огляд та порівняльний аналіз
Ріскологія Методи верифікації інформації порівняльний аналіз метод пошуку протиріч
Пристрій перетворення цифрової інформації з її шифруванням
Елементи цифрової системи передачі інформації
Розрахунок елементів цифрової системи передачі інформації
Розрахунок радіоприймального пристрою цифрової системи передачі інформації
Проектування устрою виконує задані функції перетворення цифрової інформації
Методи та засоби цифрової корекції зображення в оптико електронні
Методи розрахунку складових та структурну схему цифрової станції
© Усі права захищені
написати до нас