Шукати в цьому блозі

Хто Вам більше подобається і кому Ви надаєте перевагу?

РОЗДІЛ "ІНФОРМАТИКА"11-15


11. Логічні основи комп’ютерних систем. Алгебра висловлень і комп’ютер. Базові логічні елементи. Комбінаційні схеми та їх побудова. Поняття скінченного автомата. Приклади побудови функціональних схем цифрових автоматів.

Алгебра висловлювань і комп’ютер
Світ формул алгебри висловлювань – світ надзвичайно цікавий, і особливим є те, що велика кількість логічних задач розв’язується за єдиним алгоритмом, а це означає, що є можливість розібратися в тому, як ЕОМ складає розклад, враховує багато різних чинників  при розв’язуванні досить реальних практичних задач.
         Підкреслю, що при розв’язанні складних задач уміння створювати з простих умов передачі управління складні умови, що формулюються за допомогою алгебри висловлювань,  дозволяє робити програми більш простими і ефективними. Це означає, що алгебра висловлювань необхідна для програміста, потреба в ній може виникнути при розв’язанні не тільки логічної задачі, а й задачі на обчислення, графічної, або задачі символьної обробки.
Алгеброю логіки називають розділ математичної логіки, який вивчає загальні властивості виразів, складених із окремих висловлень.
Об'єктами алгебри логіки є розповідні речення, відносно кожного з яких можна говорити, істинне воно чи хибне. Такі речення називаються простими висловленнями.
Наприклад: Число 8 ділиться на 2;
Берлін - столиця Франції;
Перше висловлення є простим та істинним, бо однозначно можна сказати, що дійсно число 8 ділиться на 2. Друге висловлення теж просте, але хибне, бо всім відомо, що Берлін не столиця Франції.
Над простими висловленнями можна виконувати такі логічні операції: кон'юнкція, диз'юнкція, імплікація, еквіваленція та заперечення. В результаті виконання цих операцій із простих висловлень утворюються складні. Якщо ми з’єднаємо сполучником і висловлення "число 8 ділиться на 2" і висловлення "число 8 ділиться на 4", то отримаємо складне висловлення "число 8 ділиться на 2 і на 4".
В алгебрі логіки всі висловлення розглядаються лише з точки зору логічного значення. Вважається, що кожне висловлення або істинне, або хибне, і ні одне висловлення не може бути і істинним, і хибним. Істинне висловлення А позначається А = 1, а хибне висловлення В позначається В = 0
Операція кон’юнкція
З'єднання двох простих висловлювань А і В за допомогою сполучника І називається логічним множенням або кон'юнкцією, а результат операції - логічним добутком.
Операцію кон'юнкція в більшості випадків позначають знаком ^ (використовують і знаки & , · ). В звичайній мові цій операції відповідає сполучник "І". Запис А ^ В читається "а кон'юнкція в" або "а і в" Правило істинності для кон'юнкції :
Висловлення А = а ^ в істинно, якщо істинні його вхідні складові. Вихід буде дорівнювати 0, якщо хоч би одна з вхідних величин дорівнює нулю.
Таблиця істинності операції кон'юнкція:
А
В
А ^ В
0
0
0
0
1
0
1
0
0
1
1
1

Операція диз’юнкція
Для позначення операції диз'юнкція використовують знак V, який в звичайній мові відповідає сполучнику АБО. Сполучник АБО ми використовуємо в двох значеннях: виключаючому і невиключаючому. Пояснимо це на прикладах.
1. Розглянемо речення: " Володя вчора в 6 годин вечора читав книгу або їхав в автобусі на стадіон" .Сполучник АБО використано в невиключаючому розумінні - Володя міг читати і одночасно їхати в автобусі. Одне не виключає іншого.
2. Розглянемо ще одне речення: "Володя вчора спостерігав за матчем із західної або східної трибуни". Тут сполучник АБО має виключаючий характер - дві описані ситуації виключають одна одну: не можна спостерігати один і той же матч одночасно з двох протилежних трибун
В розглянутій алгебрі висловлень сполучник АБО буде використовуватись тільки в невиключаючому розумінні З'єднання двох простих висловлень А і В у одне за допомогою сполучника АБО, вжитого в невиключаючому змісті називається логічним додаванням або диз'юнкцією, а одержане складне висловлення - логічною сумою.
Висловлення А = а v в істинне, якщо істинне хоча б одне з складових вхідних висловлень. Якщо всі вхідні складові висловлення хибні, то вихідний сигнал також хибний.
В математиці прикладом диз'юнкції може служити нестрога нерівність, наприклад: "3 <= 7". Така нерівність вважається істинною, бо з двох її складових частин "3 < 7" та "3 = 7" перша частина істинна. Вірною буде і нерівність "3 >= 3". Але в нерівності "7 <= 3" жодна з складових частин не буде істинною ("7 < 3" та "7 = 3"), тому і складене висловлення буде хибним.
Діаграма Ейлера для ілюстрації операції кон'юнкція матиме наступний вигляд:
Така ж діаграма буде ілюструвати об'єднання множин, тому знаки диз'юнкції "v" та об'єднання "U" схожі між собою та схожі на літеру "і" (разом).
Таблиця істинності операції диз'юнкція:
А
В
А v В
0
0
0
0
1
1
1
0
1
1
1
1
Операція імплікація
З'єднання двох висловлень в одне з використанням звороту " Якщо…, то…" називається операцією логічного слідування або
Імплікацією.
         Указання виконати операцію імплікації над висловленнями А і В записується так: А->В (читається " Якщо А, то В" або " В слідує з А") Висловлення АаВ буде хибне тільки в тому випадку, якщо А=1, В=0.
У людській мові міркування частіше за усе являють собою ланцюжки висловлень. Ці висловлення часто мають умовний характер, тобто стверджують, що деяке висловлення істинне при умові, що істинне інше висловлення. Наприклад: "Якщо у даного трикутника бічні сторони рівні, то рівні і кути при основі". У загальному вигляді таке міркування записують таким чином: "Якщо істинне А, то істинне і В", або коротше "Якщо А, то В" записують таким чином: "Якщо істинне А, то істинне і В", або коротше "Якщо А, то В".
Таке висловлення називають імплікацією висловлень А і В і позначають А -> В. Висловлення А називають умовою, а висловлення В - наслідком.
Візьмемо А = "Зараз добра погода", В = "Я піду на прогулянку". Тоді А > В означає: "Якщо зараз добра погода, то я піду на прогулянку". Зрозуміло, що якщо зараз погода погана, ми не чекаємо виконання наслідків, і при будь-якому наслідку імплікацію вважаємо істинною. Єдиний випадок, коли імплікація вважається хибною, є істинність умови і хибність наслідку.
На звичайну мову операція імплікація може бути перекладена за допомогою виразів: "якщо …, то …", "з … слідує …". Операція імплікація тільки частково відповідає змісту сполучника "якщо …, то …" звичайної мови, де він використовується для вираження причинної залежності, і умова та висновок повинні бути зв'язані між собою за змістом. У математичній логіці змістом висловлень нехтують, залишаючи на увазі лише істинність або хибність вихідних висловлень. Наприклад: "Якщо 2+2=4, то Земля обертається навколо Сонця" - істинна імплікація.
Таблиця істинності операції імплікація:
А
В
А => В
0
0
1
0
1
1
1
0
0
1
1
1
Операція еквіваленція
З'єднання двох простих висловлень А і В у одне з використанням звороту " … тоді і тільки тоді, коли …", називається операцією еквівалентності. Висловлення, над якими проводиться ця операція розміщуються замість крапок. Указання виконати операцію еквівалентності над висловленнями А і В записується так: А<->В (читається: "А еквівалентне В ").
Еквіваленція буде істинна тоді і тільки тоді, коли вхідні величини одночасно істинні або одночасно хибні.
Таблиця істинності операції еквіваленція:
А
В
А <=> В
0
0
1
0
1
0
1
0
0
1
1
1
На звичайну мову операція еквіваленція може бути перекладена за допомогою виразів: "… тоді і тільки тоді, коли …", "… якщо і тільки якщо …", "… еквівалентне …".
Операція заперечення
Запереченням висловлення А називається таке складене висловлення ùA (не А), яке істинне тоді, коли А хибне, і хибне тоді, коли А істинне.
Дана таблиця показує зв'язок між А та ùA.
А
ùA
1
0
0
1
На звичайну мову операція заперечення може бути перекладена за допомогою виразів: не; неправильно, що … Для побудови заперечення треба додати до даного висловлення частку "ні", або вилучити її, якщо вона вже присутня.
Розглянемо два види логічних виразів:
1)        Прості логічні вирази. Простий логічний вираз – це два арифметичні вирази, з’єднані символом відношення (порівняння). Символи відношень між величинами у мовах програмування записуються так: > - більше, < - менше, >= - більше або дорівнює (не менше), <= - менше або дорівнює (не більше), = - дорівнює, <> - не дорівнює.
2)        Складені логічні вирази. Складені логічні вирази – це прості логічні вирази, до яких застосовані логічні операції
Пріоритет логічних операцій.
Для логічних операцій запроваджено такій пріоритет (черговість) виконання :
1)    not (найвищий),
2)    and,
3)    or.
Операції одного пріоритету виконуються по черзі зліва направо.
Наприклад, 1).Нехай  х – змінна цілого типу. Складений вираз
 (x = 0) or (x> 1) and (x< 3)  істинний лише для двох значень х: 0 і 2.
2).Переконайся, що складений логічний вираз
(x = 5) ornot (x< 0) and (x<= 2)  істинний, якщо х набуде одного з значень 0, 1, 2, 5.
         Послідовність виконання логічних операцій можна змінити за допомогою круглих дужок, наприклад, вираз  (x = 5) ornot ((x< 0) and (x<= 2)) істинний для всіх додатних значень змінної х.


Логічний елемент - це електронний прилад, що реалізує одну з логічних функцій. В склад серій мікросхем, що розглядаються, входить велике число логічних елементів. На принциповій схемі логічний елемент зображають прямокутником, всередині якого ставиться зображення покажчика функції. Лінії з лівої сторони прямокутника показують входи, з правої - вихід елемента. На рисунку 1 зображені основні логічні елементи, що використовуються у цифрових приладах:
Елемент І (кон'юктор);
Елемент АБО (диз юнктор)
Елемент НІ (інвертор 1)
Окрім означених існує множина логічних елементів, що виконують більш складні логічні перетворення. Ці перетворення є комбінаціями найпростіших логічних операцій. До числа таких елементів відносяться:
Рисунок 1 - Графічні позначення логічних елементів
Суматор за модулем 2 можна виконати на логічних елементах І, АБО, НІ (рисунок 2).
Рисунок 2 - Схема суматора за модулем 2
Число входів в логічних елементах різного призначення може бути різним, але входи кожного елемента рівнозначні. Деякі з них можуть при роботі в конкретних приладах не використовуватися. Входи, які не використовуються в схемах І, І-НІ з'єднують із +Uдж., а в схемах АБО, АБО-НІ, суматора за модулем 2 - із загальним проводом (0 В).
На рисунку 3 наведені приклади умовного позначення логічних елементів різних серій.
Рисунок 3 - Приклади графічного позначення логічних елементів різних серій
2 ТРИГЕРИ ТА ЇХНІ ХАРАКТЕРИСТИКИ
Найпростішими цифровими автоматами із пам'яттю є тригери. Тригер - це прилад послідовнісного типу з двома стійкими станами рівноваги, призначений для запису і зберігання інформації. Під дією вхідних сигналів тригер може переходити з одного стійкого стану в інший. При цьому напруга на його виході стрибкоподібно змінюється.
Як правило, тригер має два виходи - прямий та інверсний. Число входів залежить від структури і функцій, що виконуються тригером. За способом запису інформації тригери поділяють на асинхронні і синхронізовані (тактовані). В асинхронних тригерах інформація може записуватися безперервно і визначається інформаційними сигналами, діючими на входах у даний момент часу. Якщо інформація заноситься в тригер тільки в момент дії так званого синхронізуючого сигналу, то такий тригер називають синхронізованим або тактованим. Окрім інформаційних входів, синхронізовані тригери мають тактовий вхід (вхід синхронізації). В цифровій техніці прийняті такі позначення входів та виходів тригерів:
Q – прямий вихід тригера;
*- інверсний вихід тригера;
S - роздільний вхід установки в одиничний стан (напруга високого рівня на прямому виході Q);
R - роздільний вхід установки в нульовий стан (напруга низького рівня на прямому виході Q);
D - інформаційний вхід (на нього подається інформація, призначена для занесення в тригер);
С - вхід синхронізації;
Т - лічильний вхід.
Найбільше розповсюдження в цифрових приладах отримали RS-тригер з двома установчими входами, тактований D-тригер і лічильний Т-тригер. Розглянемо функціональні можливості кожного з них.
Асинхронний RS-тригер. В залежності від логічної структури розрізняють RS-тригери з прямими і інверсними входами. Їхні схеми і умовні позначення наведені на рисунку 4. Тригери такого типу побудовані на двох логічних елементах: 2АБО-НІ - тригер з прямими входами (рисунок 4, а), 2І-НІ - тригер з інверсними входами (рисунок 4, б). Вихід кожного з елементів під'єднаний до одного з входів іншого елемента, що забезпечує тригеру два стійких стани. Наведена таблиця 1.1 істинності для кожного з цих тригерів.
Рисунок 4 - Схеми та умовні позначення RS-тригерів
aftvin
Таблиця 1 - Таблиці істинності асинхронних RS-тригерів
S
R
http://www.refine.org.ua/images/referats/4889/image016.gif
http://www.refine.org.ua/images/referats/4889/image017.gif
http://www.refine.org.ua/images/referats/4889/image018.gif
http://www.refine.org.ua/images/referats/4889/image019.gif
http://www.refine.org.ua/images/referats/4889/image020.gif
http://www.refine.org.ua/images/referats/4889/image021.gif
http://www.refine.org.ua/images/referats/4889/image016.gif
http://www.refine.org.ua/images/referats/4889/image017.gif
http://www.refine.org.ua/images/referats/4889/image018.gif
http://www.refine.org.ua/images/referats/4889/image019.gif
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
*
0
1
1
*
1
0
1
*
1
0
0
*
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
0
*
0
1
0
*
0
0
1
*
1
0
1
*
1

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

Приклади побудови функціональних схем цифрових автоматів


Теоретичні відомості
Вузли і пристрої, які містять елементи пам’яті відносяться до класуавтоматів з пам’яттю.
Цифровий автомат – це пристрій, який здійснює приймання, зберігання і перетворення дискретної інформації за деяким алгоритмом.
Абстрактний цифровий автомат A визначається сукупністю п’ятиоб’єктів 
де – множина вхідних сигналів автомата А (вхідний алфавітавтомата А);
– множина станів автомата А (алфавіт станів автомата А);
– множина вихідних сигналів автомата А (вихіднийалфавіт автомата А);
– функція переходів автомата А, яка відображає (Х´ S)®S, тобто cтавить у відповідність будь-якій парі елементів добутку множин (Х´ S) елемент множини S;
– функція виходів автомата А, яка задає відображення (Х´ S)®Yабо
S ®Y.
За способом формування функції виходів розрізняють наступні типиавтоматів: автомат Мілі, автомат Мура (рис.1).
В абстрактному автоматі Мілі функція виходів задає відображення(Х´ S)®Y.
Автомат Мілі характеризується системою рівнянь:
.
Автомат Мура – системою рівнянь:
.
Синтез цифрових автоматів з пам’яттю можна розділити на наступні
етапи:
1) кодування;
2) вибір елементів пам’яті автомата;
3) вибір структурно - повної системи елементів (типу автомату);
4) побудова рівнянь булевих функцій виходів і збудження автомата;
5) побудова функціональної схеми автомата.

                           
                     








                       




                         …                           










     Автомат Мілі                                                    Автомат Мура
Рис.1. – Структурні схеми автоматів з пам’яттю
Розглянемо кожний із етапів детально.

1.1.Кодування
Процес заміни букв алфавітів S, Y , X цифрового автомата двійковими
векторами називається кодуванням і може бути описаний таблицею (табл. 3,табл. 4, табл. 5). В лівій частині таблиці перераховуються всі букви (наприклад вхідного алфавіту), а в правій – двійкові вектори, які ставляться у відповідність цим буквам.
      Таблиця 1 – Таблиця переходів         Таблиця 2 – Таблиця виходів
Стан
автомата
Вхідні  сигнали
x1
x2
s1
s2
s1
s2
s2
s1
s3
s3
s2


Стан
автомата
Вхідні  сигнали
x1
x2
s1
y1
y3
s2
y2
y4
s3
y1
y2










Функція переходів –; Функція виходів .
Розглянемо кодування букв алфавітів S, X,Y.
Таблиця 3. Таблиця 4. Таблиця 5
Вихідні сигнали
Код
вихідних сигналів
y1
00
y2
01
y3
10
y4
11


Стан
автома-та
Код
вхідних сигналів
x1
0
X2
1


Стан
автомата
Код
стану
s1
00
s2
01
s3
10











Таблиця переходів і виходів після кодування має вигляд:

Таблиця 6 – Таблиця переходів Таблиця 7 – Таблиця виходів
Стан
автомата
Вхідні  сигнали
0
1
00
01
00
01
01
00
10
10
01


Стан
автомата
Вхідні  сигнали
0
1
00
00
10
01
01
11
10
00
01










1.2. Вибір елементів пам’яті автомата

В якості елементів пам’яті структурного автомата використовують
D –тригери, Т – тригери, RS – тригери, JК – тригери.

Таблиці переходів тригерів.
Стан
D–тригера
Вхідний сигнал(D)
0
1
0
0
1
1
1
1


Стан
T–тригера
Вхідний сигнал(T)
0
1
0
0
1
1
1
0















Виберемо в якості елемента пам’яті Т – тригер. Складаємо таблицюфункцій збудження автомата.
Таблиця збудження елементів пам’яті будується на основі таблиціпереходів (табл. 6).

                            Таблиця переходів.

Стан
 автомата
Вхідні сигнали
x=0
x=1
 0
 1
 0
 1
 0
 1
 0
 1
 1
a1 a2
u1 u2
u1 u2










Складаємо рівняння.
Символами  u1  і  u2  в таблиці позначають функції збудження елементів пам’яті   a1  і  a2  .
Складаємо рівняння для побудови комбінаційної схеми збудженняцифрового автомата.
;
.
Таблиця виходів складається на основі таблиці 7.
Таблиця виходів

Стан
 автомата
Вхідні сигнали
x=0
x=1
 0
 0
 0
0  1
 1
 1
 0
 0
 1
a1 a2
y1 y2
y1 y2










Складаємо рівняння для побудови КС формування вихідних сигналівавтомата.
;
,
де  a1  і  a2– відповідно прямий і інвертований вихід тригера.





12.Подання (кодування) даних в пам’яті комп’ютера.
 Оперативна пам'ять є одним з найважливіших елементів комп'ютера. Саме з її процесор бере програми і вихідні дані для обробки, у неї він записує отримані результати. Назва “оперативна” ця пам'ять одержала тому, що вона працює дуже швидко, так що процесору практично не приходиться чекати при читанні даних з чи пам'яті запису в пам'ять. Однак дані, що містяться в ній, зберігаються тільки поки комп'ютер включений. При вимиканні комп'ютера вміст оперативної пам'яті стирається. Часто для оперативної пам'яті використовують позначення RAM (Random Access Memory, тобто пам'ять з довільним доступом) .
Важко недооцінити все значення і усю важливість цих невеликих по своїх розмірах плат. Сьогоднішні програми стають усе вимогливіше не тільки до кількості, але і до швидкодії ОЗУ. Однак донедавна ця область комп'ютерної індустрії практично не розвивалася (у порівнянні з іншими напрямками). Узяти хоча б відео, аудіопідсистеми, продуктивність процесорів і. т.д. Удосконалення були, але вони не відповідали темпам розвитку інших компонентів і стосувалися лише таких параметрів, як час вибірки, був доданий кеш безпосередньо на модуль пам'яті, конвеєрне виконання запиту, змінений керуючий сигнал висновку даних, але технологія виробництва залишалася колишньої, що вичерпала свій ресурс. Пам'ять ставала вузьким місцем комп'ютера, а, як відомо, швидкодія всієї системи визначається швидкодією самого повільного її елемента. І от кілька років назад хвиля технологічного бума докотилася і до оперативної пам'яті. Стали з'являтися нові типи RAM мікросхем і модулів. Зустрічаються такі поняття, як FPM RAM, EDO RAM, DRAM, VRAM, WRAM, SGRAM, MDRAM, SDRAM, SDRAM II (DDR SDRAM) , ESDRAM, SLDRAM, RDRAM, Concurrent RDRAM, Direct Rambus. Більшість з цих технологій використовуються лише на графічних платах, і у виробництві системної пам'яті комп'ютера використовуються лише деякі з них.
У пам'яті комп'ютера зберігаються програми й оброблювана інформація.
Основними характеристиками різних типів і пристроїв пам'яті є їхні обсяг і швидкодія.
Внутрішня пам'ять -- це електронні схеми. Внутрішня пам'ять дискретна -- це означає, що вона складається з певних «часток» -- комірок. Комірка пам'яті називається біт. Один біт -- це двійковий розряд пам'яті. Він зберігає двійковий код (0 або 1). Слово «біт» -- скорочення від англійського binary digit -- двійкова цифра. Отже, пам'ять комп'ютера -- це впорядкована послідовність двійкових розрядів (біт). Ця послідовність поділяється на групи по 8 розрядів; кожна така група утворює байт пам'яті.
Отже, слова «біт» і «байт» позначають назви основних одиниць виміру ємності запам'ятовувальних пристроїв. Також використовуються похідні одиниці: кілобайт (1 Кбайт (Кб) = 210 байта = 1024 байта), мегабайт:
(1 Мбайт (Мб) - 1024 Кбайт). гігабайт: (1 Гбайт (Гб) - 1024 Мбайт).
Внутрішня пам'ять складається з оперативного запам'ятовуючого пристрою (ОЗП), або оперативної пам'яті (ОП), і постійного запам'ятовуючого пристрою (ПЗП).
ОЗП -- швидка напівпровідникова енергозалежна пам'ять. В ОЗП зберігаються програма, що виконується в даний момент, і дані, з якими вона безпосередньо працює. ОЗП -- це пам'ять, яку використовують як для читання, так і для запису інформації. У разі відключення електроживлення інформація в ОЗП зникає (енергозалежність). Англійська назва ОЗП -- Random Access Memory (RAM), що перекладається як «пам'ять із довільним доступом». Цією назвою підкреслюється той факт, що процесор може звертатися до комірок пам'яті в довільному порядку, при цьому час читання/запису інформації для всіх комірок є однаковим (він вимірюється мікросекундами).
ПЗП -- швидка, енергонезалежна пам'ять. ПЗП -- це пам'ять, призначена тільки для читання. Інформація заноситься в неї один раз (зазвичай у заводських умовах) і зберігається постійно (за ввімкненого й вимкненого комп'ютера). У ПЗП зберігається інформація, наявність якої постійно необхідна в комп'ютері.
Зовнішня пам'ять комп'ютера призначена для довгострокового зберігання інформації в компактній формі. До пристроїв зовнішньої пам'яті належать гнучкі й жорсткі магнітні диски, оптичні, магнітооптичні диски тощо. Суттєве значення мають такі їхні показники, як інформаційна ємність, час доступу до інформації, надійність її зберігання, час безвідмовної роботи.
В основу запису, зберігання і зчитування інформації на пристроях зовнішньої пам'яті покладено два принципи -- магнітний і оптичний, які забезпечують зберігання інформації і після вимикання комп'ютера.
В основі магнітного запису лежить цифрова інформація (у вигляді нулів і одиниць), перетворена на змінний електричний струм, що супроводжується змінним магнітним полем. Намагнічена ділянка відповідає 1, а ненамагнічена -- 0.
Оперативний запам'ятовуючий пристрій є, мабуть, одним з найперших побудов обчислювальної машини. Оперативна пам'ять була присутня вже в першому поколінні ЕОМ по архітектурі, створених у сорокових -- на початку п'ятидесятих років двадцятого століття. За ці п'ятдесят років перемінилося не одне покоління елементної бази, на яких була побудована пам'ять.
ЕОМ першого покоління по елементній базі були вкрай ненадійними. Так, середнє брешемо роботи до відмовлення для ЕОМ “ENIAC” складала 30 хвилин. Швидкість рахунка при цьому була не порівнянна зі швидкістю рахунка сучасних комп'ютерів. Тому вимоги до збереження даних у пам'яті комп'ютера при відмовленні ЕОМ були суворіше, ніж вимоги до швидкодії оперативної пам'яті. Унаслідок цього в цих ЕОМ використовувалася енергонезалежна пам'ять.
Енергонезалежна пам'ять дозволяла зберігати введені в неї дані тривалий час (до одного місяця) при відключенні харчування. Найчастіше як енергонезалежну пам'ять використовувалися ферритові сердечники. Вони являють собою тор, виготовлених зі спеціальних матеріалів -- ферритів. Ферріти характеризуються тим, що петля гістерезиса залежності їхньої намагніченості від зовнішню магнітну підлогу носить практично прямокутний характер.
Унаслідок цього намагніченість цього сердечника міняється стрибками (положення двоїчного 0 чи 1).
Пам'ять на ферритових сердечниках працювала повільно і неефективно: адже на перемагнічування сердечника був потрібно час і затрачалося багато електричної енергії. Тому з поліпшенням надійності елементної бази ЕОМ енергонезалежна пам'ять стала витіснятися енергозалежною -- більш швидкою, ощадливої і дешевий. Проте, учені різних країн як і раніше ведуть роботи з пошуку швидкої енергозалежної пам'яті, що могла б працювати в ЕОМ для критично важливих додатків, насамперед військових.
Машинне слово — машинозалежна і платформозалежна величина, що вимірюється в бітах або байтах (тритах або трайтах), що дорівнює розрядності регістрів процесораі/або розрядності шини даних (зазвичай певний ступінь двійки). На ранніх комп'ютерах розмір слова збігався також з мінімальним розміром адресованої інформації (розрядністю даних, розташованих за однією адресою); на сучасних комп'ютерах мінімальним блоком інформації, що адресуються, зазвичай є байт, а слово складається з декількох байтів. Машинне слово визначає наступні характеристики апаратної платформи:
§  Розрядність даних, що оброблюються процесором;
§  Розрядність адресованих даних (розрядність шини даних);
§  Максимальне значення беззнакового цілого типу, що безпосередньо підтримується процесором: якщо результат арифметичної операції перевершує це значення, то відбувається переповнення;
§  Максимальний об'єм оперативної пам'яті, безпосередньо адресується процесором.
Двійкове кодування 
Представлення інформації у двійковій системі використовувалася людиною з давніх часів. Так, жителі островів Полінезії передавали необхідну інформацію за допомогою барабанів: чергування дзвінких і глухих ударів.
 Звук над поверхнею води поширювався на досить велику відстань, таким чином «працював» полінезійський телеграф. У телеграфі в XIX-XX століттях інформація передавалася за допомогою азбуки Морзе - у виглядіпослідовності з точок і тире. Часто ми домовляємося відкривати вхідні двері тільки по «умовним сигналом» - комбінації коротких і довгих дзвінків. Самюел Морзе в 1838 р . винайшов код - телеграфну абетку - систему кодування символів короткими і довгими посилками для передачі їх по лініях зв'язку, відому як «код Морзе» або «морзянка». Сучасний варіант міжнародного «коду Морзе» (International Morse) з'явився зовсім недавно - у 1939 році, коли була проведена останнє коригування. Своя система існує і в обчислювальній техніці - вона називається двійковим кодуванням і заснована на представленні даних послідовністю всього двох знаків: 0 та 1. Ці знаки називаються двійковими цифрами, по-англійськи - binary digit або скорочено bit (біт). Одним бітом можуть бути виражені два поняття: 0 або 1 (так чи ні, чорне або біле, істина або брехня і т.п.). 
Кодування чисел
 
Питання про
 кодування чисел виникає з тієї причини, що в машину не можна або нераціонально вводити числа в тому вигляді, в якому вони зображаються людиною на папері. По-перше, потрібно кодувати знак числа. По-друге, з різних причин, які будуть розглянуті нижче, доводиться іноді кодувати й іншу частину числа. Кодування цілих чисел здійснюватися через їх подання до двійковій системі числення: саме в цьому вигляді вони й містяться в осередку. Один біт відводитися при цьому для представлення знака числа (нулем кодується знак "плюс", одиницею - "мінус"). Для кодування дійсних чисел існує спеціальний формат чисел з плаваючою комою. Число при цьому представляється у вигляді: N = M * q p, де M - мантиса, p - порядок числа N, q - основа системи числення. Якщо при цьому мантиса M задовольняє умові 0,1 <= | M | <= 1 то число N називають нормалізованим. 
Кодування тексту
 
Для кодування літер та інших символів, що використовуються в друкованих документах, необхідно закріпити за кожним
 символом числовий номер - код. В англомовних країнах використовуються 26 прописних і 26 малих літер (A ... Z, a ... z), 9 знаків пунктуації (.,:! ";? ()), Пробіл, 10 цифр, 5 знаків арифметичних дій (+,-,* , /, ^) і спеціальні символи (№,%, _, #, $, &,>, <, |, \) - всього трохи більше 100 символів. Таким чином, для кодування цих символів можна обмежитися максимальним 7-розрядним двійковим числом (від 0 до 1111111, у десятковій системі числення - від 0 до 127). 
Кодування графічної інформації
 
У відеопам'яті знаходиться двійкова інформація про зображення, що виводиться на екран. Майже всі створені, в опрацюванні чи переглядаються за допомогою комп'ютера зображення можна розділити на дві великі частини - растрову і
 векторну графіку. Растрові зображення є одношаровою сітку точок, які називаються пікселями (pixel, від англ. Picture element). Код піксела містить інформації про його кольорі. На противагу растровій графіцівекторне зображення багатошаровий. Кожен елемент векторного зображення - лінія. Кожен елемент векторного зображення є об'єктом, який описується за допомогою математичних рівнянні. Складні об'єкти (ламані лінії, різні геометричні фігури) представляються у вигляді сукупності елементарних графічних об'єктів. 
Кодування звуку
 
На комп'ютері працювати зі звуковими файлами почали в 90-х роках. В основі цифрового кодування звуку лежить -
 процес перетворення коливань повітря в коливання електричного струму і подальша дискретизація аналогового електричного сигналу. Кодування та відтворення звукової інформації здійснюється за допомогою спеціальних програм (редактор звукозапису). 
Часова дискретизація - спосіб перетворення звуку в цифрову форму шляхом розбивання звукової хвилі на окремі маленькі тимчасові ділянки де амплітуди цих ділянок квантуються (їм присвоюється певне значення). Це проводиться за допомогою аналого-цифрового перетворювача, розміщеного на звуковій платі. Таким чином, безперервна залежність амплітуди
 сигналу від часу замінюється дискретної послідовністю рівнів гучності. Сучасні 16-бітові звукові карти кодують 65536 різних рівнів гучності або 16-бітну глибину звуку (кожному значенню амплітуди звук. Сигналу присвоюється 16-бітний код) Якість кодування звуку залежить від: 
1. глибини кодування звуку - кількість рівнів звуку
 
2. частоти дискретизації - кількість змін рівня сигналу в одиницю
 

Архівація даних - це злиття кількох файлів чи каталогів в єдиний файл - архів.
Стиснення даних - це скорочення обсягу вихідних файлів шляхом усунення надлишкової інформації.
Для виконання цих завдань існують програми-архіватори, які забезпечують як архівацію, так і стиснення даних. За допомогою спеціальних алгоритмів архіватори видаляють з файлів надлишкову інформацію, а при зворотній операції розпаковування вони відновлюють інформацію у первісному вигляді. При цьому стиснення та відновлення інформації відбувається без втрат.
Стиснення без втрат актуальне при роботі з текстовими і програмними файлами, у задачах криптографії.
Існують також методи стиснення із втратами. Вони видаляють з потоку інформацію, яка незначно впливає на дані або взагалі не сприймається людиною. Такі методи стиснення застосовуються для аудіо- та відеофайлів, деяких форматів графічних файлів.
Методи стиснення даних без втрат
 На сьогодні розроблено багато способів стискання без втрат, в основі їх лежать такі методи кодування:
§  Кодування Хаффмана (англ. Huffman) - в основі лежить той факт, що деякі символи в тексті можуть траплятися частіше середньої частоти повторень, а інші - рідше.
§  Кодування Лемпеля-Зіва (англ. Lempel, Ziv) - використовує факт неодноразового повторення фрагментів тексту, тобто послідовностей байтів.
§  Групове кодування RLE. Використовується для зображень з великими одноколірними ділянками. Зображення, в яких мало сусідніх пікселів однакового кольору, не придатні для стиснення по методу RLE. Розмір стиснутого файлу в такому разі може перевищувати розмір вихідного файлу.
Завдання архівації
Досі йшлося про одне призначення архівації даних - економніше використання носіїв інформації. Однак за допомогою архівації можна виконувати цілий комплекс завдань:
§  Зменшення обсягу файлів. Це завдання виконується за допомогою методів стискання, що були розглянуті вище. Зменшення файлів актуальне не лише для економії вільного місця на дисках, а й для прискорення передачі файлів по мережі. Якщо дисковий простір можна "нарощувати" шляхом придбання сучасніших дисків більшої ємності, то швидкість передавання ще довго стримуватиме збільшення розміру файлів, що передаються.
§  Резервне копіювання. У процесі експлуатації комп'ютера не виключені ситуації, що загрожують невідновною втратою інформації (несправність пристрою накопичувача або дефекти на поверхні жорсткого диска, неправильні операції з файлами або випадкове знищення файлів, чи руйнування інформації комп'ютерним вірусом). Для збереження важливої інформації застосовується резервне копіювання на зовнішні носії (магнітооптичні диски, диски CD-R і CD-RW, вінчестери). Резервне копіювання виконується за допомогою спеціальних утиліт, що забезпечують створення компактних архівів. Одна з таких утиліт, Microsoft Backup, входить до комплекту Windows.
§  Архівація при шифруванні даних. Ця операція виконується з метою зменшення імовірності злому криптосистеми. Доведено, що чим менша кореляція (взаємозв'язок) між блоками вхідної інформації, тим нижча імовірність злому. Процедура архівації, знищуючи надмірну інформацію, ліквідує кореляції у вхідному потоці.
Архівні формати й архіватори
Для роботи з архівами існують програми, що називаються архіваторами.
Перші програми-архіватори з'явилися в середині 80-х років. Вони були зорієнтовані, насамперед, на роботу в MS-DOS і підтримували популярні архівні формати: ARC, ZIP, LZH, ARJ, RAR, ICE тощо. Тогочасні архіватори дозволяли створювати архівні файли та розкривати архіви, переглядати архіви, сортувати файли в архіві, виводити вміст архіву иа екран, знищувати файли в архіві. Існувала також група архіваторів (PKLITE, LZE,..), які запаковували дані у саморозпаковувані архіви - файли з розширеннями exe, com.
В MS-DOS програми-архіватори викликаються командним рядком з чи-сленними параметрами. Параметри забезпечують великі можливості, хоча й створюють труднощі пересічному користувачеві у роботі з архіваторами.
Значно зручнішою стала робота з архівами з появою ОС Windows 9.x і Windows-версій архіваторів.
Розглянемо принципи роботи з архіваторами на прикладі програми WinRAR.
WinRAR - потужний архіватор і менеджер архівів, який має зручну графічну оболонку й підтримує технологію Drag and Drop. Програма WinRAR дозволяє працювати з архівними файлами типу rar, zip, cab, arj.
Запускається WinRAR будь-яким з можливих способів, передбачених у Windows. Якщо піктограми WinRAR немає на робочому столі або на панелі інструментів Windows, то найпростіше запустити WinRAR з головного меню (Пуск - Программы - WinRAR - WinRAR).


13. Засоби парольної ідентифікації та адміністрування.
Практичне застосування ідентифікації та аутентифікації для різних сервісів
Вступ Ідентифікація дозволяє суб'єктові (користувачеві, процесу, що діє від імені певного користувача, або іншому апаратно-програмному компоненту) назвати себе (повідомити своє ім'я). За допомогою аутентифікації друга сторона переконується, що суб'єкт дійсно той, за кого він себе видає. Як синонім слова "аутентифікація" іноді використовують словосполучення "перевірка достовірності".
Основні поняття
Аутентифікація буває односторонньою (зазвичай клієнт доводить свою достовірність серверу) і двосторонньою (взаємною). Приклад односторонньої аутентифікації - процедура входу користувача у систему. У мережевому середовищі, коли сторони ідентифікації/аутентифікації територіально рознесені, у даного сервісу є два основні аспекти: що служить аутентіфікатором (засобом підтвердження достовірності суб'єкта); як організований (і захищений) обмін даними ідентифікації/аутентифікації. Суб'єкт може підтвердити свою достовірність, пред'явивши принаймні один з фактів: щось, відоме лише йому (пароль, ідентифікаційний номер криптографічний ключ і т.п.);
щось, чим він володіє (особисту картку або інший пристрій аналогічного призначення); щось, що є частиною його самого (голос, відбитки пальців та інші свої біометричні дані). У відкритому мережевому середовищі між сторонами ідентифікації/аутентифікації не існує довіреного маршруту; це означає, що в загальному випадку дані, передані суб'єктом, можуть не співпадати з даними, отриманими і використаними для перевірки достовірності. Необхідно забезпечити захист від пасивного і активного прослуховування мережі, тобто від перехоплення, зміни і/або відтворення даних. Передача паролів у відкритому вигляді, очевидно, незадовільна; не рятує положення і шифрування паролів, оскільки воно не захищає від відтворення. Потрібні складніші протоколи аутентифікації. Надійна ідентифікація утруднена не тільки через мережеві загрози, але і з цілого ряду причин. По-перше, майже всю аутентифікаційну суть можна дізнатися, вкрасти або підробляти. По-друге, є суперечність між надійністю аутентифікації, з одного боку, і зручностями користувача і системного адміністратора з іншого. Так, з міркувань безпеки необхідно з певною частотою просити користувача повторно вводити аутентифікаційну інформацію (адже на його місце може сісти хтось інший), а це не тільки клопітно, але і підвищує імовірність того, що хтось може підглянути за вводом даних. По-третє, надійніший засіб захисту завжди дорожчий.
Парольна аутентифікація
Головна перевага парольної аутентифікації - простота і звичність. Паролі давно вбудовані в операційні системи та інші сервіси. При правильному використанні паролі можуть забезпечити прийнятний для багатьох організацій рівень безпеки. Проте, по сукупності характеристик їх слід визнати найслабкішим засобом перевірки достовірності. Щоб пароль запам'ятовувався, його часто роблять простим (ім'я подруги, назва спортивної команди і т.п.). Проте простий пароль неважко вгадати, особливо якщо знати пристрасті даного користувача. Проте, наступні заходи дозволяють значно підвищити надійність парольного захисту:
накладення технічних обмежень (пароль повинен бути не дуже коротким, він повинен містити букви, цифри, знаки пунктуації і т.п.);
управління терміном дії паролів, їх періодична зміна; обмеження доступу до файлу паролів;
обмеження числа невдалих спроб входу в систему (це утруднить застосування "методу грубої сили"); навчання користувачів;
використання програмних генераторів паролів (така програма, ґрунтуючись на нескладних правилах, може генерувати тільки благозвучні паролі, що запам'ятовуються).
Одноразові паролі
Найвідомішим програмним генератором одноразових паролів є система S/KEY компанії Bellcore. Ідея цієї системи полягає в наступному. Хай є одностороння функція f (тобто функція, обчислити зворотну до якої за прийнятний час не є можливим). Ця функція відома і користувачеві, і серверу аутентифікації. Нехай, є секретний ключ K, відомий тільки користувачеві. На етапі початкового адміністрування користувача функція f застосовується до ключа K n разів, після чого результат зберігається на сервері. Після цього процедура перевірки достовірності користувача виглядає таким чином:
сервер присилає на призначену для користувача систему число (n-1);
користувач застосовує функцію f до секретного ключа K (n-1) разів і відправляє результат по мережі на сервер аутентифікації;
сервер застосовує функцію f до отриманого від користувача значення і порівнює результат з раніше збереженою величиною. У разі збігу достовірність користувача вважається встановленою, сервер запам'ятовує нове значення (прислане користувачем) і зменшує на одиницю лічильник (n). Система S/KEY має статус Internet-стандарту (RFC 1938).
Сервер аутентифікації Kerberos
Kerberos - це програмний продукт, розроблений в середині 1980-х років в Масачусетському технологічному інституті і зазнав з тих пір низки принципових змін. Клієнтські компоненти Kerberos присутні в більшості сучасних операційних систем. Kerberos призначений для вирішення наступного завдання. Є відкрита (незахищена) мережа, у вузлах якої зосереджені суб'єкти - користувачі, а також клієнтські і серверні програмні системи. Кожен суб'єкт володіє секретним ключем. Щоб суб'єкт C міг довести свою достовірність суб'єктові S (без цього S не стане обслуговувати C), він повинен не тільки назвати себе, але і продемонструвати знання секретного ключа. C не може просто послати S свій секретний ключ, по-перше, тому, що мережа відкрита (доступна для пасивного і активного прослуховування), а, по-друге, тому, що S не знає (і не повинен знати) секретний ключ C. Потрібний менш прямолінійний спосіб демонстрації знання секретного ключа. Система Kerberos є довіреною третьою стороною (стороною, якій довіряють всі), що володіє секретними ключами обслуговуваних суб'єктів і допомагає їм у попарній перевірці достовірності. Щоб за допомогою Kerberos дістати доступ до S (звичайно це сервер), C (як правило - клієнт) посилає Kerberos запит, що містить відомості про нього (клієнтові) і про запрошувану послугу. У відповідь Kerberos повертає так званий квиток, зашифрований секретним ключем сервера, і копію частини інформації з квитка, зашифровану секретним ключем клієнта. Клієнт повинен розшифрувати другу порцію даних і переслати її разом з квитком серверу. Сервер, розшифрувавши квиток, може порівняти його вміст з додатковою інформацією, присланою клієнтом. Співпадіння свідчить про те, що клієнт зміг розшифрувати призначені йому дані (адже вміст квитка нікому, окрім сервера і Kerberos, недоступний), тобто продемонстрував знання секретного ключа. Значить, клієнт - саме той, за кого себе видає. Підкреслимо, що секретні ключі в процесі перевірки достовірності не передавалися по мережі (навіть у зашифрованому вигляді) - вони тільки використовувалися для шифрування.
Ідентифікація/аутентифікація за допомогою біометричних даних
Біометрія це сукупність автоматизованих методів ідентифікації і/або аутентифікації людей на основі їх фізіологічних і поведінкових характеристик. До фізіологічних характеристик належать особливості відбитків пальців, сітківки і рогівки очей, геометрія руки та особи і т.п. До поведінкових характеристик відносяться динаміка підпису (ручний), стиль роботи з клавіатурою. На стику фізіології і поведінки знаходяться аналіз особливостей голосу і розпізнавання мови. Біометрією у всьому світі займаються дуже давно, проте довгий час все, що було пов'язане з нею, відрізнялося складністю і дороговизною. Останнім часом попит на біометричні продукти, в першу чергу у зв'язку з розвитком електронної комерції, постійно та інтенсивно росте. Це зрозуміло, оскільки з погляду користувача набагато зручніше пред'явити себе самого, ніж щось запам'ятовувати. Попит народжує пропозицію, і на ринку з'явилися відносно недорогі апаратно-програмні продукти, орієнтовані в основному на розпізнавання відбитків пальців. Робота з біометричними даними організована таким чином. Спочатку створюється і підтримується база даних характеристик потенційних користувачів. Для цього біометричні характеристики користувача знімаються, обробляються, і результат обробки (біометричний шаблон) заноситься в базу даних (початкові дані, такі як результат сканування пальця або рогівки, зазвичай не зберігаються). Надалі для ідентифікації (і одночасно аутентифікації) користувача процес зняття і обробки повторюється, після чого проводиться пошук в базі даних шаблонів. У разі успішного пошуку особа користувача і її достовірність вважаються встановленими. Для аутентифікації досить провести порівняння з одним біометричним шаблоном, вибраним на основі попередніх введених даних. Зазвичай біометрію застосовують разом з іншими аутентифікаторами, такими, наприклад, як інтелектуальні карти. Іноді біометрична аутентифікація є лише першим рубежем захисту і служить для активізації інтелектуальних карт, що зберігають криптографічні секрети; у такому разі біометричний шаблон зберігається на тій же карті. Активність в області біометрії дуже велика. Організований відповідний консорціум (див. www.biometrics.org/), активно ведуться роботи по стандартизації різних аспектів технології (формату обміну даними, прикладного програмного інтерфейсу і т.п.), публікується маса рекламних статей, в яких біометрія підноситься як засіб забезпечення надбезпеки.
Управління доступом
Існує логічне і ролеве управління доступом. Логічне управління доступом - це основний механізм багатокористувацьких систем, покликаний забезпечити конфіденційність і цілісність об'єктів і, до деякої міри, їх доступність (шляхом заборони обслуговування неавторизованих користувачів). Тема логічного управління доступом - одна з найскладніших в області інформаційної безпеки. Річ у тому, що саме поняття об'єкту (а тим більше видів доступу) міняється від сервісу до сервісу. Для операційної системи до об'єктів відносяться файли, пристрої і процеси. Стосовно файлів і пристроїв зазвичай розглядаються права на читання, запис, виконання (для програмних файлів), іноді на видалення і додавання. Окремим правом може бути можливість передачі повноважень доступу іншим суб'єктам (так зване право володіння). Процеси можна створювати і знищувати. Сучасні операційні системи можуть підтримувати і інші об'єкти. Ролеве управління доступом передбачає, що між користувачами і їх привілеями з'являються проміжні сутності - ролі. Для кожного користувача одночасно можуть бути активними декілька ролей, кожна з яких дає йому певні права. Ролевий доступ нейтральний по відношенню до конкретних видів прав і способів їх перевірки; його можна розглядати як об'єктно-орієнтований каркас, що полегшує адміністрування, оскільки він дозволяє зробити підсистему розмежування доступу керованою при якому завгодно великому числі користувачів, перш за все за рахунок встановлення між ролями зв'язків, аналогічних спадкоємству в об'єктно-орієнтованих системах. Крім того, ролей повинно бути значно менше, ніж користувачів. В результаті число зв'язків, що адмініструються, стає пропорційним сумі (а не добутку) кількості користувачів і об'єктів, що по порядку величини зменшити вже неможливо. Ролеве управління доступом оперує наступними основними поняттями: користувач (людина, інтелектуальний автономний агент і т.п.); сеанс роботи користувача; роль (зазвичай визначається відповідно до організаційної структури); об'єкт (суть, доступ до якої розмежовується; наприклад, файл ОС або таблиця СУБД); операція (залежить від об'єкту; для файлів ОС - читання, запис, виконання і т.п.; для таблиць СУБД - вставка, видалення і т.п., для прикладних об'єктів операції можуть бути складнішими); право доступу (дозвіл виконувати певні операції над певними об'єктами). Існує статичне і динамічне розділення обов'язків. Статичне розділення обов'язків накладає обмеження на приписування користувачів ролям. У простому випадку членство в деякій ролі забороняє приписування користувача певній множині інших ролей. У загальному випадку дане обмеження задається як пара "множина ролей - число" (де множина полягає, принаймні, з двох ролей, а число повинне бути більшим за 1), так що ніякий користувач не може бути приписаний вказаному (або більшому) числу ролей із заданої множини. Наприклад, може існувати п'ять бухгалтерських ролей, але політика безпеки допускає членство не більше ніж у двох таких ролях (тут число=3). Динамічне розділення обов'язків відрізняється від статичного тільки тим, що розглядаються ролі, одночасно активні (мабуть, в різних сеансах) для даного користувача (а не ті, яким користувачі статично приписані). Наприклад, один користувач може грати роль і касира, і контролера, але не одночасно; щоб стати контролером, він повинен спочатку закрити касу. Тим самим реалізується так зване тимчасове обмеження довіри, що є аспектом мінімізації привілеїв.

Генератори паролів
 Secure Генератор паролів 2,2
Alawar
VipNet

14.Архівування та резервне копіювання даних.
Архівація даних - це злиття кількох файлів чи каталогів в єдиний файл - архів.
Стиснення даних - це скорочення обсягу вихідних файлів шляхом усунення надлишкової інформації.
Для виконання цих завдань існують програми-архіватори, які забезпечують як архівацію, так і стиснення даних. За допомогою спеціальних алгоритмів архіватори видаляють з файлів надлишкову інформацію, а при зворотній операції розпаковування вони відновлюють інформацію у первісному вигляді. При цьому стиснення та відновлення інформації відбувається без втрат.
Стиснення без втрат актуальне при роботі з текстовими і програмними файлами, у задачах криптографії.
Існують також методи стиснення із втратами. Вони видаляють з потоку інформацію, яка незначно впливає на дані або взагалі не сприймається людиною. Такі методи стиснення застосовуються для аудіо- та відеофайлів, деяких форматів графічних файлів.
Архіватор — програмне забезпечення, що використовується для стиснення інформації.
При збереженні, резервному копіюванні інформації тощо часто буває бажано стиснути файли так, щоб вони займали якомога менше місця. Це робиться за допомогою програм, які звуться архіваторами. Ці програми не тільки стискають інформацію в окремому файлі, але можуть і об'єднати в один архів групу файлів.
Існує багато архіваторів. Серед них найбільш відомі: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO.
Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівовують «на льоту» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта dblspace для операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).
Існує декілька методів стиснення інформації, що міститься у файлах. Мабуть, найпростішим із них є метод Хаффмана, який полягає в заміні стандартних 8-бітових ASCII-кодів бітовими рядками змінної довжини в залежності від частоти використання символу так, щоб символи, що використовуються частіше, мали меншу довжину. До речі, легко зрозуміти, що у текстах найчастіше зустрічається символ «пробіл», ASCII-код якого має номер 32. Можна поширити цю ідею на пари, трійки і т. д. символів. При цьому можна одержати суттєвий виграш. Дійсно, візьміть, наприклад, дві пари символів «по» та «хщ». Ви можете назвати багато слів із першим сполученням, тоді як інше зустрічається дуже рідко. А при стандартному ASCII-кодуванні на кожне зі сполучень витрачається порівну бітів — по 16. Серед інших методів, які широко застосовуються в архіваторах для стиснення інформації у файлах, назвемо лише метод Лемпела-Зіва.
Зауважимо нарешті, що комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим.
Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в декілька разів більша ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більша за ступінь надлишковості текстових даних. Іншим фактором, що впливає на ступінь надлишковості є прийнята система кодування. Прикладом систем кодування можуть бути звичайні мови спілкування, які є ні чим іншим, як системами кодування понять та ідей для висловлення думок. Так, встановлено, що кодування текстових даних за допомогою засобів української мови дає в середньому надлишковість на 20-25% більшу ніж кодування аналогічних даних засобами англійської мови.
Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Коли методи стиснення даних застосовуються до готових файлів, то часто замість терміну "стиснення даних" вживають термін "архівування даних", стиснений варіант даних називають архівом, а програмні засоби, що реалізують методи стиснення називаються архіваторами.
В залежності від того, в якому об'єкті розміщені дані, що підлягають стисненню розрізняють:
1.    Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності;
2.    Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;
3.    Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації (як правило, засобами операційної системи).
Існує багато практичних алгоритмів стиснення даних, але всі вони базуються на трьох теоретичних способах зменшення надлишковості даних. Перший спосіб полягає в зміні вмісту даних, другий - у зміні структури даних, а третій - в одночасній зміні як структури, так і вмісту даних.
Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. До таких типів даних відносяться відео- та аудіодані, а також графічні дані. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. Прикладами форматів стиснення з втратами інформації можуть бути: JPEG (Joint Photographic Experts Group) для графічних даних; MPG - для для відеоданих; MP3 - для аудіоданих.
Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графічних даних; AVI - для відеоданих; ZIP, ARJ, RAR, CAB, LH - для довільних типів даних. Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів. Однак, в основі цих методів лежать три теоретичних алгоритми:
  • алгоритм RLE (Run Length Encoding);
  • алгоритми групи KWE(KeyWord Encoding);
  • алгоритм Хафмана.
Алгоритм RLE
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Наприклад, нехай задана така послідовність даних, що підлягає стисненню:
1 1 1 1 2 2 3 4 4 4
В алгоритмі RLE пропонується замінити її наступною структурою: 1 4 2 2 3 1 4 3, де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті. Коефіцієнт стиснення, що характеризує ступінь стиснення, можна обчислити за такою формулою:
де Vx- обсяг пам'яті, необхідної для зберігання вихідної (результуючої) послідовності даних, Vn- вхідної послідовності даних.
Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд: 1 1 1 1 1 1 3 4 4 4, то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень).
Алгоритми групи KWE
В основі алгоритму стиснення за ключовими словами покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Прикладом лексичної одиниці може бути звичайне слово. На практиці, в ролі лексичних одиниць вибираються послідовності символів, що повторюються, які кодуються ланцюжком символів (кодом) меншої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник.
Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано або пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символа, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним снмвола, додається в словник. У наступний раз, коли ця фраза з'явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.
Алгоритм LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стиснуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символа К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).
Алгоритми стиснення цієї групи найефективніші для текстових даних великих обсягів і малоефективні для файлів малих розмірів (за рахунок необхідності зберігання словника).
Алгоритм Хафмана
В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Спочатку проводиться частотний аналіз вхідної послідовності даних, тобто встановлюється частота входження кожного символу, що зустрічається у ній. Після цього символи сортуються по спаданню частоти входження.
Основна ідея полягає в наступному: чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці 1.
Таблиця 1.
Символ
Частота входження
Бітовий код
A
10
00
B
8
01
C
6
100
D
5
101
E
4
110
F
4
111
Як видно з таблиці 1, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення - 93 біт, тобто майже 12 байт (без врахування довжини словника). Коефіцієнт стиснення рівний 32%. Алгоритм Хафмана універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника).
На практиці програмні засоби стиснення даних синтезують ці три "чистих" алгоритми, оскільки їх ефективність залежить від типу та обсягу даних. У таблиці 2 наведені найпоширеніші формати стиснення та відповідні їм програми-архіватори, що використовуються на практиці.
Таблиця 2.
Формат стиснення
Операційна система MS DOS
Операційна система Windows
Програма архівування
Програма розархівування
Програма архівування
Програма розархівування
ARJ
Arj.exe
Arj.exe
WinArj.exe
WinArj.exe
RAR
Rar.exe
Unrar.exe
WinRar.exe
WinRar.exe
ZIP
Pkzip.exe
Pkunzip.exe
WinZip.exe
WinZip.exe

Резе́рвне копіюва́ння (англ. backup) — процес створення копії даних на носії (жорсткому диску, дискеті тощо), призначеному для відновлення даних в оригінальному місці їх розташування в разі їх пошкодження або руйнування.
Мета
Резервне копіювання необхідно для можливості швидкого і недорогого відновлення інформації (документів, програм, настройок і т. д.) у випадку втрати робочої копії інформації з будь-якої причини.
Крім цього вирішуються суміжні проблеми:
§  Дублювання даних
§  Передача даних і робота з загальними документами.
[ред.]Вимоги до систем резервного копіювання
§  Надійність зберігання інформації. Забезпечується застосуванням відмовостійкого обладнання систем зберігання, дублюванням інформації і заміною втраченої копії іншою у разі знищення однієї з копій (в тому числі як частина відмовостійкості) .
§  Простота в експлуатації — автоматизація (по можливості мінімізувати участь людини: як користувача, так і адміністратора).
§  Швидке впровадження (просте встановлення та налаштування програм, швидке навчання користувачів).
[ред.]Види резервного копіювання
§  Повний резервування Full Backup
§  Диференціальне резервування Differential Backup
§  Додаткове резервування Incremental Backup
§  Пофайловий метод
§  Блочне інкрементальне копіювання Block Level Incremental
Повне резервування – копіювання всієї системи і всіх файлів. Щотижневе, щомісячне та щоквартальне резервне копіювання. Перше щотижневе копіювання повинне бути повним резервуванням, зазвичай виконується по п’ятницям або на вихідних під час якого копіюються всі необхідні файли. Інші копіювання що будуть виконуватися до наступного, можуть бути додатковими або диференційними, головним чином для економії часу та місця на носії.
Диференційне копіювання – кожен файл що було змінено з моменту останнього копіювання копіюється кожен раз заново. Диференційне копіювання пришвидшує процес поновлення.
Додаткове копіювання – копіювання тільки тих фалів які було змінено з тих пір як проводилось останнє повне чи додаткове копіювання. В загальному на додаткові копіювання затрачається менше часу так як копіюється менше файлів. Однак процес поновлення даних займає більше часу так як повинні відновлюватися дані останнього повного резервування плюс всі файли додаткового резервування. При цьому на відміну від диференціального резервування, змінені або нові файли не замінюють старі а додаються на носій незалежно.
Резервування клонуванням – дозволяє скопіювати цілий розділ з усіма файлами і директоріями в інший розділ або на інший носій. Здійснюється у вигляді образу або у режимі реального часу.
Віддалене резервне копіювання – сервіс що надає користувачам систему для резервного копіювання даних. Системи віддаленого резервного копіювання за часту мають вид клієнтської програми яка виконується один раз на день. Ця програма збирає, стикає, шифрує та передає дані серверам розповсюджувачів послуг резервного копіювання.
[ред.]Схеми ротації
Для резервного копіювання дуже важливим питанням є вибір схеми ротації носіїв (наприклад, магнітних стрічок). Найчастіше використовують такі схеми:
§  Одноразове копіювання;
§  Проста ротація;
§  «Дід, батько, син»;
§  «Ханойська башта»;
§  «10 наборів».
Одноразове копіювання (custom) найпростіша схема, не передбачає ротації носіїв. Всі операції проводяться вручну. Перед копіюванням адміністратор задає час початку резервування, перераховує файлові системи або каталоги, які необхідно скопіювати. Цю інформацію можна зберегти в базі, щоб її можна було використовувати знову. При одноразовому копіюванні найчастіше застосовується повне копіювання.
Проста ротація – циклічне використання носіїв для копіювання. (цикл – тиждень: певний носій на певний день тиждня)
«дід, батько, син» - ієрархічна структура використання комплекту з трьох комплектів носіїв. Раз на тиждень – батько (повне резервування), щоденне – син (додаткове або диференційне). Додатково проводиться повне копіювання – дід.
Ханойська вежа – використання комплектів носіїв даних. Кожен комплект має носії що містять місячний, тижневий, денний резерв копій.
«10 наборів» - за кожним носієм закріплюється день в який виконується копіювання при цьому при повторному використанні цей індекс зміщується на одиницю.
[ред.]Зберігання резервної копії
§  Стрічка стримера — запис резервних даних на магнітну стрічку стримера.
§  «Хмарний» бекап — запис резервних даних за «хмарною» технологією через онлайн-служби спеціальних провайдерів.
§  DVD чи CD — запис резервних даних на компактні диски.
§  HDD — запис резервних даних на жорсткий диск комп'ютера.
§  LAN — запис резервних даних на будь-яку машину всередині локальної мережі.
§  FTP — запис резервних даних на FTP-сервери.
§  USB — запис резервних даних на будь-який USB-сумісний пристрій (таке, як флеш-карта або зовнішній жорсткий диск)
§  ZIP, JAZ, MO — резервне копіювання на дискети ZIP, JAZ, MO.
[ред.]Методи боротьби з втратою інформації
Втрата інформації буває з різних причин.
[ред.]Експлуатаційні поломки носіїв інформації (жорстких дисків, дискет, CD / DVD)
Опис: випадкові поломки в межах статистики відмов, пов'язані з необережністю або виробленням ресурсу. Звичайно ж, якщо якась важлива інформація вже втрачена, то можна звернутися в спеціалізовану службу — але надійність цього не стовідсоткова.
Шлях запобігання: зберігати всю інформацію (кожен файл) мінімум у двох примірниках (причому кожен екземпляр на своєму носії даних). Для цього застосовуються:
§  RAID 1, що забезпечує відновленнянайсвіжішої інформації. Файли, розташовані на сервері з RAID, більш захищені від поломок, ніж ті, що зберігаються на локальній машині;
§  Ручне або автоматичне копіювання на інший носій. Для цього може використовуватися система контролю версій, спеціалізована програма резервного копіювання або підручні засоби на зразок cmd-файлу, які періодично запускається.
Ця причина не найпоширеніша, оскільки сучасні жорсткі диски рідко виходять з ладу.
Сучасний жорсткий диск у режимі постійно включеного комп'ютера (сервера) працює до відмови близько трьох років.
Ризик: якщо організований RAID 1 на двох однакових жорстких дисках, введених в експлуатацію одночасно, то виходити з ладу вони будуть приблизно в один і той же час! Іншими словами, якщо ви виявляєте, що перший диск почав покриватися збійними блоками, велика ймовірність, що збої є і на другому диску. Однак імовірність того, що на обох дисках вийдуть з ладу однакові сектору, порівняно незначна.
[ред.]Стихійні та техногенні лиха
Опис: шторм, землетрус, крадіжка, пожежа, прорвало водопровід — все це призводить до втрати всіх носіїв даних, розташованих на певній території.
Шлях запобігання: єдиний спосіб захисту від стихійних лих — тримати частину резервних копій в іншому приміщенні.
Опис: в цю категорію входить випадково занесене ПЗ, яке навмисно псує інформацію — віруси, черв'яки, «троянські коні». Іноді факт зараження виявляється, коли чимала частина інформації перекручена або знищена.
Шлях запобігання:
§  Встановлення антивірусних програм на робочі станції. Найпростіші антивірусні заходи — відключення автозавантаження, ізоляція локальної мережі від Інтернету, тощо
§  Забезпечення централізованого поновлення: перша копія антивірусу отримує оновлення прямо з Інтернету, а інші копії налаштовані на папку, де перша завантажує оновлення; також можна налаштувати проксі-сервер таким чином, щоб оновлення кешувати (це всі заходи для зменшення трафіку).
§  Мати копії в такому місці, до якого вірус не добереться — виділений сервер або знімні носії.
§  Якщо копіювання йде на сервер: забезпечити захист сервера від вірусів (або встановити антивірус, або використовувати ОС, для якої ймовірність зараження мала). Зберігати версії достатньої давності, щоб існувала копія, яка не контактувала із зараженим комп'ютером.
§  Якщо копіювання йде на змінні носії: частину носіїв зберігати (без дописування на них) досить довго, щоб існувала копія, що не контактувала із зараженим комп'ютером.
[ред.]Людський фактор
Опис: навмисне або ненавмисно знищення важливої інформації — людиною, спеціально написаної шкідливою програмою.
Шлях запобігання:
§  Ретельно розставляються права на всі ресурси, щоб інші користувачі не могли модифіковані чужі файли. Виняток робиться для системного адміністратора, який повинен мати всі права на все, щоб бути здатним виправити помилки користувачів, програм і т. д.
§  Забезпечити діючу систему резервного копіювання — тобто, систему, якої реально користуються і яка досить стійка до помилок оператора. Якщо користувач не користується системою резервного копіювання, вся відповідальність за збереження лягає на нього.
§  Зберігати версії достатньою давності, щоб при виявленні зіпсованих даних файл можна було відновити.
§  Перед встановленням заново ОС слід обов'язково копіювати весь вміст розділу, на якій буде встановлена ОС, на сервер, на інший розділ або на CD / DVD.
§  Оперативно оновлювати ПЗ, по якому є підозра на втрату даних.

Немає коментарів:

Дописати коментар