загрузка...
загрузка...
На головну

Безперервна і дискретна інформація

  1. Б. Спотворення інформації та дезінформація.
  2. Бойова розвідувальна інформація.
  3. Зовнішня - інформація, яку збирають за межами фірми.
  4. Генетична інформація в клітці. Гени, генетичний код і його властивості. Матричний характер реакцій біосинтезу. Біосинтез білка і нуклеїнових кислот
  5. ГЛАВА 7. ІНФОРМАЦІЯ ЯК ОБ'ЄКТ САМОСТІЙНОГО ОБІГУ
  6. графічна інформація
  7. ЦЯ І НОВА ІНФОРМАЦІЯ ТЕКСТУ

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

У разі, коли параметр сигналу приймає послідовне в часі кінцеве число значень (при цьому всі вони можуть бути пронумеровані), сигнал називається дискретним,а повідомлення, передане за допомогою таких сигналів - дискретним повідомленням.Інформація, передана джерелом, в цьому випадку також називається дискретною. Якщо ж джерело виробляє безперервне повідомлення (відповідно параметр сигналу - безперервна функція від часу), відповідна інформація називається безперервної.Приклад дискретного повідомлення - процес читання книги, інформація в якій представлена ??текстом, тобто дискретної послідовністю окремих значків (букв). Прикладом безперервного повідомлення служить людська мова, що передається модульованої звуковою хвилею; параметром сигналу в цьому випадку є тиск, що створюється цією хвилею в точці знаходження приймача - людського вуха.

Безперервне повідомлення може бути представлено безперервною функцією f(t), Заданої на деякому відрізку [А, b] (Рис. 1. 2, а). Безперервне повідомлення можна

перетворити в дискретний (така процедура називається дискретизацией).Для цього з нескінченної кількості значень цієї функції (параметра сигналу) вибирається їх певне число, яке наближено може характеризувати інші значення. Один із способів такого вибору полягає в наступному. Область визначення функції розбивається точками t1, t2, ..., tn на проміжки рівної довжини  (Рівномірна дискретизація), і безперервна функція замінюється імпульсної з деякою короткою і однаковою тривалістю імпульсів, амплітуда кожного з яких приймається постійною і дорівнює значенню функції в зазначених точках (рис. 1.2, б). Отримана таким чином імпульсна функція є дискретним поданням неперервної функції, точність якого можна необмежено поліпшувати (принаймні теоретично) шляхом зменшення довжин відрізків розбиття області значень аргументу.

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

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

Питання про способи дискретизації безперервно представленої інформації і відновлення такої інформації по її дискретного поданням (так званим «отсчетам») виник в техніці електрозв'язку істотно раніше створення ЕОМ (у зв'язку з розробкою пристроїв цифрової тимчасової комутації для телефонних станцій). Теоретичну базу для його вирішення (в разі рівномірної дискретизації) заклав в 1933 р радянський вчений В. А. Котельников, який сформулював стала згодом класичною теорему, що носить його ім'я.

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

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

Істотно, що теорема Котельникова не просто «теорема про можливість», але носить конструктивний характер. Відновлення безперервного сигналу по його дискретного образу реалізується шляхом підсумовування ряду

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

Одиниці кількості інформації: імовірнісний і об'ємний підходи.Визначити поняття «кількість інформації» досить складно. У вирішенні цієї проблеми існують два основні підходи. Історично вони виникли майже одночасно. В кінці 1940 рр. один з основоположників кібернетики американський математик Клод Шеннон розвинув імовірнісний підхід до вимірювання кількості інформації, а роботи по створенню ЕОМ привели до «об'ємному» підходу.

Імовірнісний підхід. Розглянемо як приклад досвід, пов'язаний з киданням правильної гральної кістки, що має N граней (найбільш поширеним є випадок шестигранною кістки: N = 6). Результатом даного досвіду може бути випадання межі з одним з наступних знаків: 1, 2, ..., N

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

H = f (N), (1.1)

а сама функція / є зростаючою, неотрицательной і певної (в розглянутому нами прикладі) для N = 1, 2, ..., 6.

Розглянемо процедуру кидання кістки більш докладно:

1) готуємося кинути кістку; результат досвіду невідомий, тобто є деяка невизначеність; позначимо її Н1;

2) кістка кинута; інформація про результат даного досвіду отримана; позначимо кількість цієї інформації через I;

3) позначимо невизначеність даного досвіду після його здійснення через H2.

За кількість інформації, яке отримано в ході здійснення досвіду, приймемо різниця невизначеностей «до» і «після» досвіду:

I = H1 - H2.

Очевидно, що в разі, коли отриманий конкретний результат, що була невизначеність знята (H2 = 0), і, таким чином, кількість отриманої інформації збігається з початковою ентропією. Інакше кажучи, невизначеність, укладена в досвіді, збігається з інформацією про результат цього досвіду.

Наступним важливим моментом є визначення виду функції f у формулі (1.1). Якщо варіювати число граней N ічісло бросаний кістки (позначимо цю величину через М), то загальне число випадків (векторів довжини М, складаються із знаків 1, 2, ..., N) Дорівнюватиме N у ступені М:

X = NM. (1..2)

Так, у разі двох бросаний кістки з шістьма гранями маємо Х = 62 = 36. Фактично кожен результат X є деяка пара (X1, Х2), де X1 та Х2 - відповідно результати першого і другого бросаний (X -загальна кількість таких пар).

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

f (6M) = Mf (6).

Дану формулу можна поширити і на випадок будь-якого N:

f {NM) = Mf (N). (1.3)

Прологаріфміруем ліву і праву частини формули (1.2): lnХ = MlnN, M =ln X / ln N.

Підставляємо отримане для М значення в формулу (1.3):

позначивши через K позитивну константу, отримаємо f (X) = КlnХ, або, з урахуванням (1.1), Н = KlnN. зазвичай приймають К = 1 / ln2. Таким чином,

H = log2N. (1.4)

Вираз (1.4) - формула Хартлі.

Важливим при введенні будь-якої величини є питання про те, що приймати за одиницю її виміру. очевидно, Н буде дорівнює одиниці при N = 2. Інакше кажучи, в якості одиниці приймається кількість інформації, пов'язане з проведенням досвіду, що складається в отриманні одного з двох рівноймовірно результатів (прикладом такого досвіду може служити кидання монети, при якому можливі два результати: «орел» і «решка»). Така одиниця кількості інформації називається «біт».

Усе N результатів розглянутого вище досвіду є рівноімовірними і тому можна вважати, що на «частку» кожного результату доводиться одна N-я частина загальної невизначеності досвіду: (log2N) / N. При цьому ймовірність i-го результату Рi дорівнює, очевидно, 1/ N.

Таким чином,

 (1.5)

Формула (1.5) приймається за міру ентропії і в разі, коли ймовірності різних результатів досвіду неравновероятни(Тобто Pi можуть бути різні). Формула (1.5) називається формулою Шеннона.

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

Н = log2 34 = 5 біт.

Однак в словах російської мови (так само як і в словах інших мов) різні літери зустрічаються неоднаково часто. У табл. 1.1 наведені ймовірності частоти вживання різних знаків російського алфавіту, отримані на основі аналізу дуже великих за обсягом текстів.

Скористаємося для підрахунку H формулою (1.5):  біт. отримане значення Н, як і можна було припустити, менше обчисленого раніше. величина Н, обчислюється за формулою (1.4), є максимальною кількістю інформації, яка могла б припадати на один знак.

аналогічні підрахунки Н можна провести і для інших мов, наприклад використовують латинський алфавіт, - англійської, німецької, французької та ін. (26 різних букв і «пробіл»). За формулою (1.4) отримаємо

H = log227 »4,76 біт.

Як і в разі російської мови, частота появи тих чи інших знаків неоднакова. Якщо розташувати всі букви даних мов в порядку убування ймовірностей, то отримаємо такі послідовності:

англійську мову: «пробіл», Е, Т, А, О, N, R, ...

німецьку мову: «пробіл», Е, N, I, S, Т, R, ...

французьку мову: «пробіл», Е, S, A, N, I, T, ...

Розглянемо алфавіт, що складається з двох знаків: 0 та 1. Якщо вважати, що зі знаками 0 і 1 в двійковому алфавіті пов'язані однакові ймовірності їх появи (Р (0) = Р (1) = 0,5), то кількість інформації на один знак при довічним кодуванні

H = log22 = 1 біт.

Таким чином, кількість інформації (в бітах), укладену в довічним слові, дорівнює числу двійкових знаків у ньому.

Об'ємний підхід. У двійковій системі числення знаки 0 і 1 будемо називати битами(Від англійського виразу Binary digits - виконавчі цифри). Відзначимо, що творці комп'ютерів віддають перевагу саме двійковій системі числення тому, що в технічному пристрої найбільш просто реалізувати два протилежних фізичних стану. У комп'ютері біт є найменшій можливій одиницею інформації.

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

Для зручності використання введені і більші, ніж біт, одиниці кількості інформації. Так, двійкове слово з восьми знаків містить один байтінформації, 1024 байта утворюють кілобайт(Кбайт), 1024 кілобайт - мегабайт(Мбайт), а 1024 мегабайта - гігабайт(Гбайт).

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

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

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

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

Спроби розглянути категорію інформації з позицій основного питання філософії привели до виникнення двох протиборчих концепцій - так званих атрибутивноїи функціональної.«Атрібутісти» кваліфікують інформацію як властивість всіх матеріальних об'єктів, тобто як атрибут матерії. «Функціоналістів» пов'язують інформацію лише з функціонуванням складних, що самоорганізуються. Обидва підходи, швидше за все, неповні. Справа в тому, що природа свідомості по суті своїй є інформаційною, тобто свідомість - менш загальне поняття по відношенню до категорії «інформація». Не можна визнати коректними спроби зведення більш загального поняття до менш загального. Таким чином, інформація і інформаційні процеси, якщо мати на увазі рішення основного питання філософії, опосередковують матеріальне і духовне, тобто замість класичної постановки цього питання виходить два нових: про співвідношення матерії та інформації і про співвідношення інформації і свідомості (духу).

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

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

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

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

Визначення інформації як філософської категорії не тільки зачіпає фізичні аспекти існування інформації, але і фіксує її соціальну значущість.

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

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

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

Зауважимо, що при всіх висновках формули Больцмана явно або неявно передбачається, що макроскопічне стан системи, до якого відноситься функція ентропії, реалізується на мікроскопічному рівні як поєднання механічних станів дуже великого числа частинок (молекул), що утворюють систему. У завданнях кодування і передачі інформації, для вирішення яких Хартлі і Шенноном була розвинена імовірнісна міра інформації, використовувалося дуже вузьке технічне розуміння інформації, майже не має відношення до повного об'єму цього поняття. Таким чином, більшість міркувань, що використовують термодинамічні властивості ентропії стосовно інформації нашої реальності, носять спекулятивний характер. Зокрема, є необгрунтованими використання поняття «ентропія» для систем з кінцевим і невеликим числом станів, а також спроби розширювального методологічного тлумачення результатів теорії поза досить примітивних механічних моделей, для яких вони були отримані.

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

Розглянемо деякий набір властивостей інформації:

- Запам'ятовуваність;

- Передання;

- Відтворюваність;

- Перетворювані;

- Стирання.

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

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

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

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

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

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

Підводячи підсумок сказаному, відзначимо, що робляться (але аж ніяк не завершені) зусилля вчених, що представляють різні галузі знання, побудувати єдину теорію, яка покликана формалізувати поняття інформації та інформаційного процесу, описати перетворення інформації в процесах самої різної природи. Рух інформації є сутність процесів управління, які суть прояв іманентної активності матерії, її здатності до саморуху. З моменту виникнення кібернетики управління розглядається стосовно до всіх форм руху матерії, а не тільки до вищих (біологічної і соціальної). Багато проявів руху в неживих - штучних (технічних) і природних (природних) - системах також мають загальні ознаки управління, хоча їх досліджують в хімії, фізиці, механіці в енергетичній, а не в інформаційній системі уявлень. Інформаційні аспекти в таких системах становлять предмет нової міждисциплінарної науки - синергетики.

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

Кодування інформації. абстрактний алфавіт. Інформація передається у вигляді повідомлень. Дискретна інформація записується за допомогою деякого кінцевого набору знаків, які будемо називати буквами,не вкладаючи в це слово звичного обмеженого значення (типу «російські літери» чи «латинські букви»). Буква в даному розширеному розумінні - будь-який із символів, які деяким угодою встановлені для спілкування. Наприклад, при звичній передачі повідомлень російською мовою такими знаками будуть російські літери - великі та малі, знаки пунктуації, пробіл; якщо в тексті є числа - то і цифри. Взагалі буквою будемо називати елемент деякого кінцевого безлічі (набору) відмінних один від одного знаків. Безліч знаків, в якому визначено їх порядок, назвемо алфавітом (загальновідомий порядок знаків у російській алфавіті: А, Б, ..., Я).

Розглянемо деякі приклади алфавітів.

1. Алфавіт прописних російських букв:

АБВГДЕЁЖЗІЙКЛМНОПРСТУФХЦЧШЩ'ИЬЕЮЯ

2. Алфавіт клавіатурних символів ПЕОМ IBM (русифікована клавіатура):

1234567890- =

~! @ # $% ^ & * () _ +

qwertyuiop []

QWERTYUIOP {}

asdfghjkl ;: "

ASDFGHJKL: «»

zxcvbnm,. /

ZXCVBNM <>?

йцукенгшщзх'

ЙЦУКЕНГШЩЗХ'

фивапролдже

ФИВАПРОЛДЖЕ

ячсмітьбю

ЯЧСМІТЬБЮ

3. Алфавіт знаків правильної шестигранної гральної кістки:

4. Алфавіт арабських цифр:

5. Алфавіт шістнадцятирічних цифр:

0123456789ABCDEF

Цей приклад, зокрема, показує, що знаки одного алфавіту можуть утворюватися з знаків інших алфавітів.

6. Алфавіт довічних цифр:

0 1

Алфавіт 6 є одним із прикладів так званих «довічних» алфавітів, т. Е. Алфавітів, що складаються з будь-яких двох знаків. Іншими прикладами є виконавчі алфавіти: «точка», «тире» (? ?); «Плюс», «мінус» (+ -).

7. Алфавіт прописних латинських букв:

8. Алфавіт римської системи числення:

9. Алфавіт мови блок-схем зображення алгоритмів:

10. Алфавіт мови програмування Паскаль (див. Гл. 3).

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

Розглянемо деякі приклади кодів.

1. Азбука Морзе в російській варіанті (алфавітом, складеним з алфавіту російських заголовних букв і алфавіту арабських цифр, ставиться у відповідність алфавіт Морзе):

Мал. 1.3. Процес передачі повідомлення від джерела до приймача

2. Код Трісіме (знакам латинського алфавіту ставляться у відповідність комбінації з трьох знаків: 1, 2, 3):

Код Трісіме є прикладом так званого рівномірного коду (такого, в якому все кодові комбінації містять однакове число знаків - в даному випадку три). Приклад нерівномірного коду - азбука Морзе.

Кодування чисел знаками різних систем числення буде розглянуто далі.

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

Комп'ютер вважають універсальним перетворювачем інформації. Тексти на природних мовах і числа, математичні і спеціальні символи - одним словом все, що в побуті або в професійній діяльності може бути необхідно людині, повинно мати можливість бути введеним в комп'ютер.

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

Спробуємо підрахувати найбільш коротку довжину такої комбінації з точки зору людини, зацікавленого у використанні лише одного природного алфавіту - скажімо, англійської: 26 букв слід помножити на 2 (великі та малі) - разом 52; 10 цифр; вважатимемо, 10 знаків; 10 розділових знаків (три види дужок, пробіл і ін.); знаки звичних математичних дій; кілька спеціальних символів (типу #, $, & і ін.) - разом приблизно 100. Точний підрахунок тут не потрібен, оскільки нам треба буде розв'язати просту задачу: маючи рівномірний код з груп по N довічних знаків, скільки можна утворити різних кодових комбінацій? Відповідь очевидна: К = 2N. Отже, при N = 6 К = 64 - явно мало, при N = 7 К = 128 - цілком достатньо.

Однак для кодування декількох (хоча б двох) природних алфавітів (плюс всі зазначені вище знаки) і цього недостатньо. Мінімально достатнє значення N ветом випадку 8; маючи 256 комбінацій двійкових символів, цілком можна вирішити зазначене завдання. Оскільки 8 двійкових символів становлять 1 байт, то говорять про системах «байтового» кодування.

Найбільш поширені дві такі системи: EBCDIC (Extended Binary Coded Decimal Interchange Code) і ASCII (American Standard Cod Information Interchange). Перша історично тяжіє до «великим» машинам, друга частіше використовується на міні- і мікроЕОМ (в тому числі і на персональних комп'ютерах). Ознайомимося докладніше саме з ASCII, створеної в 1963 р

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

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

Для подання букв російської мови (кирилиці) в рамках ASCII було запропоновано кілька версій. Спочатку був розроблений стандарт під назвою ЯКІ-7, який опинився по ряду причин вкрай невдалим; нині він практично не використовується.

У табл. 1.6 приведена часто використовувана в нашій країні модифікована альтернативне кодування. У ліву частину входять вихідні коди ASCII, в праву частину (розширення ASCII) вставлені букви кирилиці замість букв німецького, французького алфавітів (не збігаються з написання з англійськими), грецьких букв, деяких спеціальних символів.

Знаків алфавіту ПЕОМ ставляться у відповідність шістнадцятиричні числа за правилом: перша - номер стовпця, друга - номер рядка. Наприклад: англійська «А» - код 41, російська «і» - код А8.

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

Відзначимо, що навіть 8-бітна кодування недостатня для кодування всіх символів, які хотілося б мати в розширеному алфавіті. всі перешкоди

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

Перешкоди в передачі інформації - цілком звичайна справа в усіх сферах професійної діяльності та в побуті. Один із прикладів був уже приведений, інші приклади - розмова по телефону, в трубці якого «тріщить», водіння автомобіля в тумані і т.д. Найчастіше людина цілком справляється з кожної із зазначених завдань, хоча і не завжди віддає собі звіт, як він це робить (тобто неалгоритмічних, а виходячи з якихось асоціативних зв'язків). Відомо, що природна мова має велику надмірністю(В європейських мовах - до 7%), чим пояснюється велика завадостійкість повідомлень, складених із знаків алфавітів таких мов. Прикладом, який ілюструє стійкість російської мови до перешкод, може служити пропозиція «в словах все гласне замінено буквою о». Тут 26% символів «вражені», однак це не призводить до втрати сенсу. Таким чином, в даному випадку надмірність є корисним властивістю.

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

Перша теорема Шеннонадекларує можливість створення системи ефективного кодування дискретних повідомлень, у якій середнє число двійкових символів на один символ повідомлення асимптотично прагне до ентропії джерела повідомлень (у відсутності перешкод).

Завдання ефективного кодування описується тріадою:

тут X, В - відповідно вхідний і вихідний алфавіт; під безліччю х, можна розуміти будь-які знаки (літери, слова, пропозиції); В - безліч, число елементів якого в разі кодування знаків числами визначається підставою системи числення (наприклад, т= 2). Кодує пристрій зіставляє кожному повідомленням х, з X кодову комбінацію, складену з ni символів безлічі В. Обмеженням даного завдання є відсутність перешкод. Потрібно оцінити мінімальну середню довжину кодової комбінації.

Для вирішення даного завдання повинна бути відома ймовірність Pt появи повідомлення xi, якому відповідає певна кількість символів і, алфавіту В. Тоді математичне очікування кількості символів з В визначиться наступним чином:

Цьому середньому числу символів алфавіту В відповідає максимальна ентропія Нmax = ncplog т. Для забезпечення передачі інформації, що міститься в повідомленнях X кодовими комбінаціями з В, має виконуватися умова Нmax ? H (х), або ncplog m ? -Pi logPi. В цьому випадку закодоване повідомлення має надмірність пср ? H (x) / logm, nmin = H (x) / logm.

коефіцієнт надмірності

Випишемо ці значення в вигляді табл. 1.7. маємо:

т. е. код практично не має надмірності. Видно, що середнє число двійкових символів прагне до ентропії джерела повідомлень.

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

Доказ теореми грунтується на наступних міркуваннях. спочатку послідовність Х = {хi } Кодується символами з В так, що досягається максимальна пропускна здатність (канал не має перешкод). Потім в послідовність з В довжини п вводиться r додаткових символів і по каналу передається нова послідовність з n + r символів. ці r додаткових символів забезпечують надмірність кодування інформації і дозволяють протидіяти перешкодам. Число можливих послідовностей довжини п + r більше числа можливих послідовностей довжини п. Безліч всіх послідовностей довжини п + r може бути розбите на і підмножин, кожному з яких порівняна одна з послідовностей довжини п. Вплив перешкоди на послідовність з n + r символів виводить її з відповідного підмножини з ймовірністю, що залежить від r. Це дозволить визначити на приймальній стороні каналу, яким подмножеству належить перекручена перешкодами прийнята послідовність довжини п + r, і тим самим відновити вихідну послідовність довжини п.

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



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

КОНСПЕКТ ЛЕКЦІЇ | Історія розвитку обчислювальної техніки. | покоління ЕОМ | Системи числення, представлення чисел в різних системах числення. | Надоперативна пам'ять з прямим і асоціативним доступом. (РОН і Кеш-пам'ять). Віртуальна пам'ять. | організація пам'яті | захист пам'яті | адресація пам'яті | Диспетчер пам'яті | сегментація пам'яті |

загрузка...
© um.co.ua - учбові матеріали та реферати