Застосування штрих-коду для кодування інформації

Размещено на http://www.allbest.ru/

1

58

Размещено на http://www.allbest.ru/

ДИПЛОМНА РОБОТА

застосування штрих-коду для кодування інформації

ЗМІСТ

Вступ

1. Теоретичні відомості

1.1 Побудова та класифікація штрихових кодів

1.2 Деякі поняття теорії інформації

1.2.1 Міра інформації

1.2.2 Інформаційна ентропія

1.2.3 Умовна ентропія. Iнформацiя, що мiститься в одному дослiдi вiдносно iншого

1.2.4 Надлишковість

1.2.5 Цiннiсть iнформацiї

1.2.6 Експотенціальний закон збiльшення числа повiдомленнь

1.3 Коди з виявленням та виправленням помилок

1.3.1 Кодування інформації

1.3.2 Коди з виявленням та виправленням помилок

2. Огляд найбільш вживаних типів штрихових кодів

2.1 Загальний огляд

2.2 Тип EAN-13, UPC та EAN-8

2.3 Code39 та CODABAR

2.4 INTERLEAVED 2 OF 5

3. Створення самокорегуючого штрихового коду

3.1 Постановка задачі

3.2 Хід роботи

4. Результати та їх аналіз

4.1 Початкові результати

4.2 Кінцевий результат

5. Програми

5.1 Iнструкція користувача

5.2 Текст програм

Висновки

Джерела

ВСТУП

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

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

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

Чому саме штрихові коди вийшли на перше місце серед безлічі відомих засобів ідентифікації? Що зумовило їхню перевагу в більшості практичних додатків перед іншими оптичними засобами, не говорячи вже про такі, як магнітні або, скажемо, пов'язані з застосуванням радіоізотопів? Як вже було сказано, переваги різних засобів оцінюються з точки зору надійності, простоти застосування і економічності. Штрихові коди характеризуються високою надійністю. До них застосовні ті засоби захисту від помилок, що широко використовуються в зв'язку та комп'ютерній справі. За рахунок деякої надмірності можна створювати самоконтролюючі і самокорректуючі коди, тобто такі, що здатні шляхом перевірки по спеціальним алгоритмам забезпечити відшукання помилок і навіть їх автокоррекцію за умови, що кількість помилкових знаків в коді не перевищує встановленої межі (звичайно 65-70%). При існуючих засобах захисту лінійного коду, що забезпечують імовірність помилки не більш однієї на 30 млн. зчитаних знаків, надмірність коду залишається в розумних межах -- звичайно це одна контрольна цифра.

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

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

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

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

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

1. Теоретичні відомості

1.1 Способи побудови штрихових кодів та методи класифікації

Розглянемо основнi принципи та правила, що використовуються про створеннi штрихових кодiв i якi є обов'язковими для будь-якого їх типу. Одразу потрiбно зазначити, що інформація яку ми кодуемо представлена в двійковому виді, тобто кодується двома значеннями: '0' та '1'. В штриховому кодуванні існує два способи задання цих значень, першим є спосіб, коли значення '0' та '1' кодуються відповідно двома кольорами - білим та чорним. Наприклад: бітова послідовність 10110011101100011 буде мати слідуюче штрихове представлення:

(рис 1)

В цьому способі штрихи що відповідають '0' та '1' мають одинакову ширину. В разі якщо в бінарній послідовності йдуть одне за одним кілька одинакових n значень '0' чи '1' їм буде відповідати білий чи чорний штрих n-кратної ширини.

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

(рис2)

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

(рис 3)(рис 4)

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

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

(рис 5)

Детально даний тип штрихового коду буде розглянуто пізніше.

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

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

1.2 Деякі поняття теорії інформації

1.2.1 Мiра iнформацiї

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

Наприклад, повiдомлення про те, що в технiчнiй системi управлiння вийшов з ладу один з двох однаково надiйних (або, краще сказати, ненадiйних) підсилювачів, i повiдомлення, що Н. народила хлопчика, зв'язанi з однiєю i тіею же різноманітністю - з появою одного з двох рівноможливих фактiв.

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

Вiдзначимо, що поняття кiлькостi iнформацiї, укладеної в тому або iншому повiдомленнi, зв'язане з iмовiрнiстю цього повiдомлення, тобто з деякою статистичною сукупнiстю. Введемо бiльш точне визначення iнформацiї як деякої кiлькiсної величини - деякої мiри.

По визначенню кiлькiсть власної iнформацiї, укладеної в повiдомленнi Аi рiвна логарифму його iмовiрностi, взятому зі зворотнім знаком

I (Аі) = -log(P(Ai)). (1.14)

Знак мiнус в формулi (1.14) введений для того, щоб зробити цей вираз iстотно позитивним [0?Р(Аi)?1, ? логарифм Р (Ai) - величина вiдємна]. Виразу (1. 14) можна придати вигляд

I(Аi)=log 1/P(Ai) (1.15)

з якого слiдує, що чим менша iмовiрнiсть появи повiдомлення Ai, тим бiльшою кiлькiстю iнформацiї воно володiє.

Сенс вводу логарифмичної мiри в виразах (1.14) i (1.15) полягає в наданнi кiлькостi iнформацiї властивостi адитивності. Справдi, якщо ми маємо дiло зi складним повiдомленням, що полягае в одночасному повiдомленнi двох фактiв Ai i Вj, i якщо цi факти (подiї) незалежнi в iмовiрносному розумiннi, то, згiдно (1.14),

I (A, Bj) = logP (AiBi).

Або, застосовуючи теорему про множення iмовiрностей, маємо

I(Аi,Bj) = - log[ Р(Аi)Р(Bj)] = -1оg Р(Ai) - log P(Вj) = I(Ai) - I(Bj). (1.16)

Іншими словами, кiлькiсть iнформацiї, вкладеної в два незалежних повiдомлення, рiвна сумi кiлькостi iнформацiї, вкладеної в кожне повiдомленнi. З наведеного вище визначення власної iнформацiї (1. 14) слiдує надто важливий висновок: з деяким повiдомленням Аi можна зв'язати поняття власної iнформацiї тiльки в тому випадку, якщо iснує поняття iмовiрностi цього повiдомлення (тобто, якщо його можна зв'язати з деяким статистичним ансамблем). Наприклад, окреме повiдомлення, не зв'язане з якою-небуть рiзноманiтнiстю, не володiє в розумiннi теорiї iнформацiї поняттям власної iнформацiї.

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

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

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

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

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

В технiчному сенсi це означає, що не можна заздалегiдь сконструювати хорошу систему (принаймнi в планi лiнiї зв'язку). Але ми маємо можливiсть будувати, самонавчальну систему, що адаптується, що з течiєю часу, з'ясовуючи iстинну статистику розподiлу повiдомлень, тобто визначаючи кiлькiсть iнформацiї, зв'язане з тим або iншим повiдомленням, зможе себе змiнювати, покращувати. Наприклад (в граничному випадку), по якому-небуть каналу надходить весь час одне i те ж повiдомлення А. В цьому випадку система визначить, що Р (А)=1 i, отже, I=0. Значить, можна просто запам'ятати це повiдомлення, а канал зв'язку вимкнути. Це i буде простим прикладом адаптацiї.

Другим важливим поняттям є вiдносна iнформацiя одного повiдомлення Sj вiдносно iншого Ai. Сенс цього поняття полягає в тому, що надходження деякого факту (повiдомлення Sj) може змiнити статистичну рiзноманiтнiсть, зв'язану з повiдомленням Аi, i внаслiдок цього власну iнформацiю повiдомлення Аi. Змiна власної iнформацiї повiдомлення A_і, що виникла через надходження повiдомлення Sj, i називається вiдносною iнформацiєю повiдомлення Sj вiдносно Ai.

Нехай iмовiрнiсть повiдомлення Аi до надходження повiдомлення Sj рiвна Р(Аi).

Тодi кiлькiсть власної iнформацiї, укладеної в повiдомленя Ai, рiвне

I (Ai) = -log P(Ai).

Iмовiрнiсть повiдомлення Аi, пiсля надходження повiдомлення Sj буде рiвна Psj(Аi), тобто являє собою умовну iмовiрнiсть Ai за умови, що Sj має мiсце. При цьому кiлькiсть iнформацiї, що мiститься в надходженнi повiдомлення Ai, рiвна

I (Ai/Sj) = - log Psj(Ai).

Тодi по визначенню iнформацiя, що мiститься в Sj вiдносно Аi, рiвна змiнi (зменшенню) власної iнформацiї повiдомлення Ai:

Isj(Ai) = I(Ai) - I(Ai/Sj) = - log P(Ai)+ log Psj(Ai) = log(Psj(Ai)/P(Ai)). (1.17)

Це нове поняття вiдносної iнформацiї зв'язане не з iмовiрнiстю повiдомлення Sj, а зi змiстом цього повiдомлення, бо саме конкретний змiст повiдомлення Sj визначає умовну iмовiрнiсть подiї Аi (Psj(Ai)). Таким чином, вiдносна iнформацiя деякого повiдомлення Sj зв'язана саме з його змiстом, а не з його власною рiзноманiтнiстю, якої може i не бути. Таким чином, навiть з окремим повiдомленням, не зв'язаним з поняттям iмовiрностi, можна зв'язати поняття iнформацiї вiдносно iншої рiзноманiтностi, якщо воно цю рiзноманiтнiсть змiнює.

В протилежнiсть власнiй iнформацiї, вiдносна iнформацiя може бути не тiльки позитивною, але i негативною. Якщо Psj(Ai) > Р(Аi), то, згiдно (1.17), Isj(Аi)=0; якщо Psj(Ai) < P(Ai), то Isj(Ai) <0. Нарештi, при Psj(Ai)=P(Ai) Isj(Аi)=0. Останнiй випадок означає, що повiдомлення Sj не змiнює рiзноманiтностi Ai i, отже, не мiстить в собi iнформацiї вiдносно повiдомлення Ai. Повертаючись до основної iнформацiйної мiри, до виразу (1.14), легко бачити, що числова величина його залежить вiд вибору основи логарифмування. Звичайно в теорiї iнформацiї в якостi основи беруть число 2; тодi числова величина кiлькостi iнформацiї, укладеної в деякому повiдомленнi Ai, рiвна

Ii=log2 Рi. (1. 18)

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

Ii=log2 (1/2) =1 двiйкова одиниця = 1бiт.

Отже, це повiдомлення володiє однiєю двiйковою одиницею iнформацiї (двiйковою тому, що в якостi основи логарифма прийняте число 2) або, як часто говорять, несе 1 бim iнформацiї (б - bit, binary digit). В якостi дiйкової одиницi iнформацiї, приймається та кiлькiсть iнформацiї, що полягає в повiдомленi про те, що вiдбулися одне з двох рiвноможливих подiй (наприклад, iнформацiя про те, що при даному пiдкидуваннi монети випав герб).

Уявимо собi далi, що деякий дослiд може закiнчитися одним з чотирьох рiвноможливих наслiдкiв. Тодi повiдомлення про те, що має мiсце деякий конкретний наслiдок, володiє iмовiрнiстю Pi=l/4. Вiдповiдно кiлькiсть iнформацiї в цьому повiдомленнi J = - 1оg(1/4)=2 бiт. Якщо ж ситуацiя дослiду настiльки невизначена, що може з'явитися будь-який з 64 рiвноможливих наслiдкiв, то кiлькiсть iнформацiї, укладеної в повiдомлення про деякий конкретний наслiдок, рiвна J = - log(1/64) = 6 бiт i т. д.

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

На кiнець розглянемо приклад. По каналу зв'язку передається пятизначне двiйкове число так, що в кожному розрядi може стояти цифра 0 або 1 з рiвною iмовiрнiстю, i поява тiєї або iншої цифри в даному розрядi не залежить вiд цифр що стоять в iнших розрядах. Визначимо, яка кiлькiсть iнформацiї мiститься в деякому числi ,що передається. Нехай для визначеностi дано число ,що передає значення 10110. Тодi iмовiрнiсть появи даного числа Ai = Рi = (1/2)5 (згiдно теоремi множення iмовiрностей). Легко бачити, що будь-яке число ,що передається володiє тiєю ж iмовiрнiстю. Тодi кiлькiсть iнформацiї, укладена в кожне число ,що передається, рiвна

I = - log Pi = - log (1/2)5= 5 бiт.

Вiдповiдно при передачi n-розрядного двiйкового числа, кiлькiсть iнформацiї на повiдомлення рiвна I = n бiт.

З прикладу видно, що при двiйковому кодуваннi повiдомлень дуже зручно застосовувати при обчисленнi кiлькостi iнформацiї логарифм з основою два.

1.2.1 Iнформацiйна ентропія

До цих пiр ми розглядали кiлькiсть власної iнформацiї, що мiститься в даному конкретному повiдомленнi Ai, i для нього ввели мiру iнформацiї (1. 14) Ii = - log Pi. Уявимо собi тепер, що в результатi проведення деякого дослiду можливi k рiзноманiтних повiдомлень (результатiв дослiду А1, А2, ..., Ak). Цей дослiд ми повторюємо велике число раз (n), наприклад n раз передаємо повiдомлення з даної вхiдної системи, i нехай з цих повiдомлень (результатiв) А1 повторюється m1 раз, А2 повторюється m2 раз i т. д. Крiм того, нехай iмовiрностi повiдомлень А1, А2, ..., Ak вiдповiдно рiвнi Р1, P2, ..., Рk. Тодi середня власна iнформацiя на одне повiдомлення буде рiвна сумi iнформацiї, подiлленої на кiлькiсть повiдомлень ,що передаються, або середня власна iнформацiя на одне повiдомлення рiвна

(- m1 logP1 - m2 logP2 - ... -mk logPk)/n.

Очевидно, межа цього вираження при n®Ґ--рівна--

k

H = - S--Pi log Pi ,(1.19)

1

бо в вiдповiдностi з законом великих чисел

при n®Ґ lim (mi/n)=Pi.

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

1. Ентропiя завжди додатня

Н і--0. (1. 20)

Дiйсно, 0 Ј--Pi Ј--1, тому log PiЈ0, тобто величина вiдємна. Отже, враховуючи знак мiнус в виразi (1.19), кожний член цiєї суми буде додатнiм, а отже, i вся сума додатня.

2. Ентропiя рiвна нулю в тому i тiльки в тому випадку, якщо iмовiрнiсть одного з результатiв рiвна одиницi, а отже, iмовiрностi всiх iнших результатiв рiвнi нулю (нагадаємо, що P1+P2+... +Pk=1). Iншими словами, ентропiя рiвна нулю, тодi коли ситуацiя повнiстю визначена, тобто результат дослiду заздалегiдь передбачено.

Дiйсно, вираз (1.19) являє собою суму додатніх величин, тому ця сума може бути рiвна нулю тiльки в тому випадку, коли кожний з її членiв Р log P рiвний нулю. Вираз Р logР рiвний нулю або при Р=1 (що очевидно, бо при Р=1 логарифм Р рiвний 0), або при Р=0. В останньому випадку має мiсце невизначенiсть, i щоб її розкрити, запишемо вираз Р logР в виглядi

PlogP= (logP)/(1/P).

Границя цього виразу рiвна межi вiдношення похiдної числiвника до похiдної знаменника

Але тiльки один результат дослiду може володiти iмовiрнiстю, рiвною одиницi, i при цьому всi iншi результатi володiють iмовiрнiстю, рiвною нулевi, тому сума (1. 19) рiвна нулю тiльки в цьому випадку i наше твердження доведене.

3. Ентропiя максимальна тодi i тiльки тодi, коли всi результати ситуацiї (дослiду) рiвноможливi. Припустимо, що наша ситуацiя може мати k результатов i всi вони рiвноможливi. Тодi Р1 = Р2.. = Рk = 1/k, оскiльки Р₁+P₂+...+Р_k=1. При цьому значення ентропiї в вiдповiдностi з (1.19) буде рiвне

Hmax=log k . (1.21)

Покажемо тепер, що ентропiя завжди менша або рiвна виразу (1. 21). Для цього складемо рiзницю

k

H - log k = - S--Pi log Pi - log k =

1

k k k

= - S--Pi log Pi - S--Pi log k = - S--Pi log 1/Pi ,

1 1 1

k

оскiльки S--Pi =1.

Скористаємось далi наступною властивiстю логарифмiчної функцiї: для будь-якого значення аргументу w має мiсце нерiвнiсть

ln w w-1. (1. 23)

Нерiвнiсть (1.23) (в лiвiй частинi стоїть натуральний логарифм) очевидно з рис. 5. Знак рiвностi має мiсце при значеннi w=1. Якщо в правій частинi (1. 22) величину 1/Рik позначимо через w i приймемо до уваги, що

log w = ln w log e,

то можна до кожного члена суми (1. 22) застосувати нерiвнiсть (1. 23). Тодi отримаємо

Оскiльки

то

H - log k Ј--0 (1.24)

Таким чином, ентропiя завжди менша або рiвна величинi log k (1.22), причому знак рiвностi має мiсце при w=1, тобто при 1/Pik=1, або при всiх Pi=1/k, що означає рiвноможливiсть всiх результатiв дослiду.

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

Всяке впорядкування ситуацiї, збiльшення її визначенностi зменшує ентропiю. Отже, вираз (1. 19), з одного боку, являє собою середню iнформацiю, яку можна очiкувати вiд повiдомлення в даних умовах, а з iншого, його можна розглядати, як мiру невизначеностi ситуацiї. Цi двi сторони, звичайно, зв'язанi мiж собою. Справдi, чим бiльш невизначена ситуацiя, тим бiльша iнформацiя буде полягати в кожному повiдомленнi про який-небуть конкретний результат. Часто в результатi деякого дослiду ми одержуємо деяку кiлькiсну величину х, що може приймати будь-яке значення в заданому iнтервалi. В цьому випадку результатом дослiду є безперервна випадкова величина, що володiє деяким законом розподiлу p (x) (рис. 6).

рис.5 рис.6

Отже, тут ми маємо дiло з нескiнченним числом можливих результатов i значить з нескiнченним числом можливих повiдомлень. Для такої ситуацiї по аналогiї з виразом (1.19) вводиться поняття ентропiї безперервного розподiлу

+Ґ

-т--p(x) log p(x) dx (1. 25)

-Ґ

1.2.3 Умовна ентропія. Iнформацiя, що мiститься в одному дослiдi вiдносно iншого

Розглянемо два дослiди а i b, вiдповiдно з результатами А1, A2, ..., Аi, ..., Am i результатами В1, B2, ..., Вj, ..., Bn i вiдомими iмовiрностями цих результатів Р(А1), Р(А2), ..., Р(Ai) i Р(В1), Р(В2), ..., Р(Bj). Вiзьмемо далi складний дослiд аb, який полягає в тому, що водночас здiйснюються дослiди а i b. Спробуємо обчислити середню власну iнформацiю, що мiститься в якому-небуть результатi складного дослiду (Ai, Bj) або, iншими словами, ентропiю дослiду ab.

По визначенню ентропiя складного дослiду рiвна

H(a,b) = -SР(Ai,Bj) log P(Ai,Вj). (1. 26)

Ij

З iншого боку, ентропiя першого дослiду a рiвна

H(a,b) = -SР(Ai) log P(Ai) (1. 27)

i

Пiдставимо далi в (1. 27) Р(Ai), що входять в перший спiвмножник кожного доданку в виглядi

P(Ai) = -SP(Ai,Вj) (1. 28).

j

Вiдзначимо, що вираз (1. 28) являє собою запис формули повної iмовiрностi для подiї Ai, тобто формулу (1. 12). Пiсля подстановки (1.28) в (1. 27) отримаємо

H(a) = -SSР(Ai,Bj) log P(Ai) (1.29)

i j

Аналогiчно ентропiя дослiду b може бути представлена в виглядi

H(b) = -SSР(Ai,Bj) log P(Вj) (1.30)

i j

Якщо a i b - незалежнi дослiди, то для кожної пари результатiв Ai i Bj

P (Ai,Bj) = P(Ai) P(Bj),

отже,

log Р(Аi,Вj)=log Р(Ai) + log Р(Bj). (1.31)

Пiдставляючи далi (1.31) в (1.26), отримаємо

H(a,b)= - SSР(Ai,Bj) log P(Ai) - SSР(Ai,Bj) log P(Вj)

i j i j

Або, маючи на увазi (1. 29) i (1. 30),

H (ab) =H (а) + H (b). (1. 32)

Таким чином, при незалежних дослiдах ентропiя складного дослiду рiвна сумi ентропiй кожного дослiду.

В бiльш загальному випадку, коли дослiди залежнi, iмовiрнiсть пари результатів Ai, Bj може бути представлена в виглядi

Р (Аi, Вj) =Р(Аi) Р(Вj). (1. 33)

Вiдповiдно

log Р (Аi,Вj) = log Р(Ai) + logPAi(Bj). (1. 33')

Тут PAi(Bj) означає умовну iмовiрнiсть результата Вj, якщо вiдомо, що дослiд а закiнчився результатом Ai.

Підставляючи (1. 33') в (1. 20), отримаємо

H(a,b) = -SSР(Ai,Bj) log P(Ai) - SSР(Ai,Bj) log PAi(Вj) (1.34)

i j i j

Перша сума в виразi (1.34) являє собою (1.29) або ентропiю дослiду а. Другу суму в (1.34) називають умовною ентропiєю дослiду b, припускаючи, що який-небуть результат дослiду а мав мiсце. Цю ентропiю дослiду b за умови дослiду а позначимо Ha(b). Тодi ентропiя складного дослiду, тобто (1. 34), може бути записана

H (а, b)=H (a) + Ha(b). (1.35)

По визначенню умовна ентропiя являє собою вираз

(1.36)

або, маючи на увазi (1. 33),

(1.37)

i j

Внутрiшня сума в виразi (1. 37), очевидно, являє собою ентропiю дослiду b за умови, що дослiд a закiнчився конкретним результатом Ai. Справдi ця внутрiшня сума нiчим не вiдрiзняється вiд виразу (1.19), за винятком того, що замiсть iмовiрностей Р(Bj) тут стоять iмовiрностi результатiв Bj при умовi, що був конкретний результат Ai.

Цю умовну ентропiю дослiду b при конкретному результатi дослiду а позначимо через HAi(b)

НАi(b) = - SРAi(Bj) log PAi(Вj) (1.38)

j

При цьому вираз (1. 37), тобто умовна ентропiя дослiду b при дослiдi a, може бути представлено як усереднення виразу (1. 38) по всiм результатам дослiду а, тобто по всiм Аi

Нa(b) = - SР(Aj)HAi(Вj) (1.39)

i

Таким чином, умовна ентропiя дослiду b при дослiдi а являє собою середню власну iнформацiю, що полягає в результатi дослiду b в середньому при будь-якому результатi дослiду а.

Розглянемо властивостi умовної ентропiї.

1. Якщо дослiди a i b незалежнi, те умовна ентропiя рiвна безумовнiй

Ha(b) = H (b). (1.40)

Властивiсть (1.40) безпосередньо слiдує з порiвняння формул (1.32) i (1.35), виведених вiдповiдно для випадкiв незалежних i залежних дослiдiв.

2. Якщо результати першого дослiду, скажемо дослiду а, повнiстю визначають результати iншого дослiду b (тобто дослiд а визначає дослiд b), то умовна ентропiя рiвна нулю

Ha (b) = 0. (1.41)

Дiйсно, бо при цьому всi РAi(Bj) рiвнi або одиницi або нулю, в вiдповiдностi з (1.38) величина HAi(b) рiвна нулю для всiх результатiв Аi дослiду а. НAi(b)=0, тому вираз (1. 39) перетворюється в нуль.

3. Умовна ентропiя завжди менша або рiвна безумовної ентропiї, тобто

Ha(b) Ј--H (b). (1.42)

Знак рiвностi має мiсце при незалежностi дослiду а i b (див. властивiсть 1).

Для доказу спiввiдношення (1. 42) утворимо рiзницю

Ha(b)-----H (b) = -SSР(Ai,Bj) log PAi(Вj) -(- SSР(Ai,Bj) log P(Вj)) = (1.43)

i j i j

= - SSР(Ai,Bj) log (P(Вj)/PAi(Вj))

i j

Застосуємо до виразу (1.43) властивiсть логарифмiчної функцiї (1. 23), поклавши тут w = Р(Bj)/PAi(Bj). Тодi

Ha(b)-----H (b) Ј log e SSР(Ai,Bj)(P(Вj)/PAi(Вj) - 1)=0

i j

Дiйсно, права частина цiєї нерiвностi легко може бути записана як

log e [SР(Ai)SР(Bj) - 1] =0

i j

що тотожно рiвна нулю. Отже, Ha(b) - H (b) Ј--0, тобто доведена нерiвнiсть (1.42). Знак рiвностi має мiсце при w=0, тобто при P(Bj)/PAi(Bj) =1 для будь-яких Аi i Bj, або тодi, коли дослiди а i b незалежнi.

Ми отримали результат, що умовна ентропiя дослiду b, якщо проведений дослiд а, завжди менша або рiвна ентропiї дослiду b. Однак умовна ентропiя дослiду b при конкретному результатi дослiду а, HAi(b) може бути i меншою i бiльшою ентропiї дослiду b, Н(b). Цей факт можна пояснити слiдуючим чином. Для одних результатiв Аi має мiсце HAi(b) < H(b), для iнших, навпаки, HAi(b) буде бiльше H(b). Але в середньому в сенсi формули (1. 39) ентропiя Hа(b) буде завжди менша або рiвна ентропiї H (b).

Пояснимо сказане прикладом.

Нехай хворий страждає яким-небуть одним з трьох захворювань B1, B2, B3. При цьому iмовiрнiсть того, що вiн страждає першим захворюванням, рiвна Р(B1)=0.98, а iмовiрностi iнших захворювань вiдповiдно рiвнi Р(B2) =P(B3) =0,01. Подальше дослiдження хворого a може мати два результата А1 i A2, причому результат А1 виключає захворювання B1, а результат A2 повнiстю пiдтверджує наявнiсть захворювання B1 i, отже, виключає захворювання B2 i В3. Обчислимо ентропiю (невизначенiсть) ситуацiї до проведення дослiдження a. Тодi

H(b)= - [P(B1) log P(B1) + P(B2) log P(B2) + P(B3) log P(B3)] =

= - [0,98 log0,98 + 0,01 log 0,01 + 0,01 log 0,01] = 0,16 бiт.

Вiдзначимо, що Р(A2) =0, 98, а Р(A1) = 0, 02, бо поява цих результатов еквiвалентна подiям B1 i notВ1. Крiм того, очевидно, що PA1(B1) = 0, PA1(B2)=PA1(B3) = 1/2, бо результат А1 виключає захворювання B1 i при цьому залишаються два рiвноiмовiрних захворювання: В2 i B3. З iншого боку, PA2(B1)=1 i PA2(B2) = PA2(B3) = 0.

Обчислимо тепер ентропiю (невизначенiсть) ситуацiї при конкретних результатах дослiдження a

НА1(b)= - [PA1(B1) log PA1(B1)+РА1(B2) log PA1(B2)+РA1(B3) log PA1(B3)] =

= 0 + 1/2log2 + 1/2log2= 1 бiт,

НА2(b)= - [PA2(B1) log PA2(B1)+PA2(B2) log PA2(B2)+PA2(B3) log PA2(B3)] =

=0 + 0 + 0 = 0.

Таким чином, ми бачимо, що результат А1 збiльшує ентропiю (невизначенiсть) ситуацiї, а результат А2 зменшує. Цей факт має просте фiзичне обгрунтування. Справдi, до проведення дослiдження a, розподiл iмовiрностей захворювань був таким, що ми могли бути майже впевненi в тому, що хворий страждає захворюванням В1, i в цьому сенсi невизначенiсть ситуацiї була надто невелика (0, 16 бiт).

Однак, якщо в результатi дослiдження a з'являється результат A1 (що в загалi-то малоймовiрно, але можливо), то в цьому випадку виявиться, що хворий може мати яке-небуть одне з двох рiвноможливих захворювань B2 або B3. В цьому випадку невизначенiсть ситуацiї виявиться вже значно бiльшою (1 бiт). Але якщо в результатi дослiду a виникне результат А2 (що вiдбувається в переважнiй бiльшостi випадкiв, в середньому в 98 випадках з 100), та це твердо вкаже на наявнiсть у хворого захворювання В1, i, отже жодної невизначенностi бiльше не буде (HA2(b)=0). Середня ж ентропiя ситуацiї b за умови проведення iспиту а буде все-таки менша, нiж Н(b)

Ha(b) = Р(А1)НA1(b)+Р(А2)НA2(b)=0, 02·1+0, 98·0=0, 02 бiт,

тобто

Ha(b) < H(b).

4. Оскiльки всяка ентропiя додатня, то вираз (1.38) iстотно додатнiй, а отже, додатня i (1.39). Отже,

Ha(b) і 0. (1.44)

Об'єднуючи (1.42) i (1.44), отримаємо

0 Ј Ha(b) Ј H (b). (1.45)

5. В якостi п'ятої властивостi умовної ентропiї виведемо тотожнiсть

Н(а) + Ha(b) = H (b) + Hb(a). (1.46)

Вираз (1.46) безпосередньо слiдує з того факту, що складний дослiд ab нiчим нe вiдрiзняється вiд дослiду ba. Отже,

H(аb) = H(ba)

або

H(a) + Ha(b) = H(b) + Hb(a).

Розглянемо тепер питання про середню iнформацiю, що мiститься в одному дослiдi вiдносно iншого, або, iнакше кажучи, про середню вiдносну iнформацiю. Нехай невизначенiсть, зв'язана з деяким дослiдом b, виражається ентропiєю H(b). Здiйснення деякого iншого дослiду а зменшує невизначенiсть дослiду b. Це виражається в тому, що умовна ентропiя ситуацiї b пiсля проведення дослiду a стає меншою, нiж ентропiя ситуацiї b, тобто

Ha(b) Ј H(b).

Різниця H(b) - Ha(b) являє собою зменшення невизначеностi дослiду b або, iншими словами, зменшення середньої власної iнформацiї в дослiдi b. Це зменшення власної iнформацiї в дослiдi b прeдcтавляє собою ту кiлькiсть iнформацiї, що несе дослiд a вiдносно дослiду b. В вiдповiдностi з цим середньою iнформацiєю одного дослiду вiдносно iншого називають вираз

I(ab) = H(b) - Ha(b). (1.47)

Враховуючи вираз (1.46), можемо записати

H(b) - Ha(b) = H(a) - Hb(a) (1. 48)

або

I(ab) = I(ba) (1. 49)

Таким чином, середня iнформацiя, що полягає в одному дослiдi вiдносно iншого, рiвна середнiй iнформацiї, укладеній в iншому дослiдi вiдносно першого. Оскiльки умовна ентропiя - величина iстотно додатня, то з (1. 47) i (1. 48) слiдує, що

I(ab) Ј H (a), I (ab) Ј H (b). (1. 50)

Нерівність (1.50) виражае той факт, що середня iнформацiя, що мiститься в одному дослiдi вiдносно iншого, менша, нiж iнформацiя, укладена в середньому в кожному результатi цього дослiду вiдносно самого себе.

Вiдноcна iнформацiя, що мiститься в конкретному результатi дослiду a, тобто в Аi, вiдносно всiх результатів дослiду b (в середньому) в вiдповiдностi з визначенням (1. 47), рiвна

I (Aib) = H (b) - HAi(b). (1.51)

Вона може бути i додатньою i вiдємною, оскiльки НАi(b) може бути i менше, i бiльше Н(b). В протилежнiсть цьому iнформацiя I(ab) завжди додатня, оскiльки На(b) завжди менше або рiвне H(b). Якщо же нас цiкавить iнформацiя, що мiститься в конкретному результаті дослiду ab (тобто в Ai) вiдносно конкретного результату дослiду b (тобто Bj), то в вирзi (1.51) слiд опустити усереднення по результатам Bj. Тодi отримаємо

I(Аi, Вj) = - log Р(Bj) - (- log PAi(Bj)) = log (PAi(Bj)/P(Bj)),

тобто вираз (1. 17).

1.2.4 Надлишковість

Маємо деяку систему дослiдів a1, a2, ..., am. Власна середня кiлькiсть iнформацiї на один результат кожного окремого дослiду рiвна його ентропiї

I(a1) = Н(a1),

I(a2) = Н(a2),

. . . . . . . . . . . . .

I(am) = Н(am),

Власна середня кiлькiсть iнформацiї на один результат складного дослiду, являючого собою сукупнiсть дослiдiв a1, ..., am, рiвна ентропiї складного дослiду I(a1, ..., am) = H(a1, ..., am).

Якщо дослiди a1, ..., am незалежнi, то в вiдповiдностi з (1.32)

H (а1, ..., am) = H(a1) + H(a2) + ... + H(am)

або

I (a1, ..., am) = SI(ai) (1.52)

i

Однак, якщо дослiди a1, ..., am залежнi, то в вiдповiдностi з (1. 32), (1. 35) i (1.42)

H(а1, ..., am) Ј H(a1) + H(a2) + ... + H(am)

Або

I (а1, ..., am) Ј I(a1) + I(a2) + ... + I(am) (1.53)

З (1. 52) i (1.53) слiдує, що з системи незалежних дослiдiв(випробувань) можна отримати бiльше iнформацiї, нiж з системи залежних. I навпаки, для отримання тiєї же iнформацiї в випадку незалежностi можна обiйтися меншою кiлькiстю випробувань. Це важливо мати на увазi при розробцi бiльш ощадливої системи iспитiв. Отже, в випадку залежних дослiдiв для отримання тiєї ж кiлькостi iнформацiї, ми повиннi проводити бiльшу кiлькiсть iспитiв, нiж це мiнiмально необхiдно, тобто вводити деяку надлишковiсть в iспитах.

Для кiлькiсної оцiнки цiєї надлишковостi вводиться коєфiцiент надлишковостi, що виражає собою вiдносне зменшення кiлькостi одержуваної iнформацiї внаслiдок залежностi мiж дослiдом

(1. 54)

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

I (ai) = log L. [див (1.21)].

В той же час, якщо символи в кодовому словi незалежнi, тобто iмовiрнiсть появи даного символу не залежить вiд того, якi символи мiстяться в iнших розрядах кодового слова, то кiлькiсть iнформацiї, що мiститься в системi символiв (тобто в кодовому словi в цiлому), рiвна

n

S I(ai) = n log L (1. 55)

i=1

Вираз (1.55) являє собою максимальну власну кiлькiсть iнформацiї, що може мiститися в кодовому словi довжиною в n символiв при алфавiтi L. Однак, якщо код мiстить обмеження, що полягає, наприклад, в неможливостi деяких комбiнацiй символiв (детермiнiстськi обмеження) або в тому, що iмовiрнiсть появи якого-небуть символа залежить вiд того, якi символи є в iнших розрядах кодового слова (ймовiрнiснi обмеження), то кiлькiсть iнформацiї, що мiститься в середньому в кожному кодовому словi, буде менша (1. 55). Цю кiлькiсть iнформацiї позначимо I(a1, ..., an). Такий код буде володiти надлишковістю, рiвною в вiдповiдностi з (1.54).

(1. 56)

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

Наведемо приклад. Розглянемо двiйково-десятковий код, що часто використовується для подання кiлькiсних величi.

0-0000

1-0001

2-0010

3-0011

4-0100

5-0101

6-0110

7-0111

8-1000

9-1001

В цьому кодi кожний розряд десяткового числа представляється 4 двiйковими розрядами.

В даному кодi можливi 10 рiзноманiтних повiдомлень, i якщо всi вони рiвноiмовiрнi (оптимальний випадок в сенсi максимума iнформацiї), то кiлькiсть iнформацiї на повiдомлення буде рiвно

I(a1, ..., a4) = log 10.

А коефiцiент надлишковостi в вiдповiдностi з (1. 50) рiвний

оскiльки тут n=4 i L=2. Отримана в цьому прикладi надлишковiсть двiйково-десяткового коду з'являється внаслiдок того, що ряд комбiнацiй в цьому кодi недопустимі. А саме, тут не мають сенсу наступнi комбiнацiї: 1010, 1011, 1100, 1101, 1111. До цих пiр ми розглядали надлишковість як небажане явище, що приводить або до необхiдностi ставити бiльше число дослiдiв, нiж це мiнiмально необхiдно, або в випадку кодування повiдомлень користуватися кодами бiльшої довжини. Однак надлишковість має позитивну сторону, так як дозволяє одержувати бiльшу надiйнiсть результатiв (дублювання дослiду), або, в випадку кодування, спецiальний ввiд надлишковостi дозволяє виявляти й виправляти помилки, що виникають в процесi передачi коду по каналу зв'язку.

1.2.5 Цiннiсть iнформацiї

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

Дiйсно, як вказано вище, повiдомлення про те, що в двухкаскадному пiдсилювачi, що зiпсувався, деякої системи управлiння зiпсувався саме перший каскад, мiстить стiльки ж iнформацiї, скiльки i повiдомлення про те, що дружина вашого товариша народила хлопчика, а саме I = -log1/2=1 бiт. Бо i в тому i в iншому випадку має мiсце свобода вибору з двох рiноможливих подiй.

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

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

Однак в рамках теорiї iнформацiї не зовсiм безнадiйний стан i з проблемою визначення цiнностi конкретних повiдомлень. Бiльш того, в цьому вiдношеннi можна скористатися викладеним математичним апаратом. Для цього визначимо спочатку кiлькiсно, що таке цiннiсть iнформацiї, цiннiсть повiдомлення. Припустимо, що кожна людина на даному вiдрiзку часу здiйснює яку-небуть цiлеспрямовану дiяльнiсть, що може мати в якостi результату деяку множину результатiв Аj. Наприклад, якщо лiкар в даний момент займається встановленням дiагнозу, то можна сказати, що ця дiяльнiсть закiнчиться трьома результатами: А1 - буде поставлений правильний дiагноз, A2 - дiагноз не буде поставлений, А3 - дiагноз буде поставлений невiрно. Кожний з цих результатiв до отримання нової iнформацiї, нового повiдомлення володiє деякою апрiорною iмовiрнiстю Р(Аj).

Ми можемо вважати, що отримане повiдомлення має яку-небуть цiннiсть в даний момент для цiєї людини, для цього споживача, якщо воно змiнює апрiорну iмовiрнiсть результату його дiяльностi, i не має цiнностi, якщо воно не змiнює цiєї iмовiрностi. Наприклад, для лiкаря, що ставить дiагноз, повiдомлення про деякий результат дослiдження даного хворого має значну цiннiсть i зовсiм цiнностi не має повiдомлення про те, що вийшов з ладу пiдсилювач в системi управлiння, бо останнє нiяк не змiнює iмовiрностi результату його дiяльностi. Тодi пiд цiннiстю деякого повiдомлення Si по вiдношенню до певного результату дiяльностi Aj будемо розумiти по аналогiї з (1.17)

. (1.57)

Iншими словами, цiннiсть даного повiдомлення по вiдношенню до даного результату дiяльностi, визначається як логарифм вiдносної змiни iмовiрностi деякого результату дiяльностi.

Аналогiчно можна ввести поняття цiнностi повiдомлення Sj по вiдношенню до деякої дiяльностi a взагалi, що мiстить ряд результатiв Aj.

Тут поняття цiнностi повiдомлення буде мати характер середньої цiнностi для всiх результатів даного виду дiяльностi

C(Si, a) =H(a) - Hsi(a). (1. 58)

Ентропiя H(а) не зв'язана з деяким дослiдом, а являє собою невизначенiсть в результатi дiяльностi даного споживача, що через iмовiрностi результатiв визначається за допомогою формули (1. 19). Нарештi, можна ввести поняття середньої цiнностi системи повiдомлень S(S1,S2, ..., Si) по вiдношенню до даної дiяльностi споживача a(a1, a2, ..., aj)

C (S, а) =H(а) - Hs(a). (1.59)

1.2.6 Експоненціальний закон збiльшення числа повiдомленнь

Всяку iнформацiю ми передаємо вiд одного джерела до iншого за допомогою певної системи символiв - кодiв, що складається з обмеженого числа знакiв - алфавiту. Наприклад, всi слова i речення в росiйськiй мовi можна передати за допомогою 32 знакiв. Тут алфавiт мiстить L=32 символа. В двiйковiй системi числення алфавiт мiстить L=2 символiв (0 i 1), в десятковiй L=10 i т. д.

Доведемо тепер, що якщо код не мiстить обмежень, те послiдовнiсть з n символiв припускає можливiсть скласти

N=Ln (1.60)

рiзноманiтних повiдомлень. В цьому i заключаеться експоненциальний закон збiльшення числа повiдомлень з збiльшенням довжини повiдомлення n.

Покажемо справедливiсть виразу (1.60) за допомогою методу математичної iндукцiї. Для цього достатньо довести два твердження: а) якщо вираз (1.60) вiрний для будь-якого n (n - цiле, додатне число), те вiн вiрний i для n+1; б) вираз (1. 60) справедливий для n=1. Очевидно, що якщо твердження (а) i (б) справедливi, те вираз (1.60) вiрний для будь-якого n.

Почнемо з твердження (б). Якщо n=1, тобто наше повiдомлення складається тiльки з одного символу, то в якостi цього символу ми можемо взяти будь-який з L, тобто число рiзноманiтних повiдомлень буде N=L. Це число i дасть формула (1. 60) при n=1.

Перейдемо до доведення твердження (а). Нехай ми маємо послiдовнiсть довжиною в n символiв. Тодi по припущенню кiлькiсть рiзноманiтних повiдомлень, що можна здiйснити за допомогою такої послiдовностi, рiвна Ln. Додамо до цiєї послiдовностi ще один символ. Тодi, підставляючи на це нове мiсце будь-який з L символiв, отримаємо з кожного старого повiдомлення L нових повiдомлень. Всього кiлькiсть нових повiдомлень буде рiвна

Nn+1 = Ln · L = Ln+1 ,

тобто ми довели, що якщо вираз (1.60) справедливий для n, то вiн справедливий i для n+1.

Формулу (1.60) можна видозмiнити слiдуючим чином. Нехай час передачi кожного символа рiвно t сек (будемо вважати, що тривалiсть передачi всiх символiв однакова). Тодi тривалiсть передачi повiдомлень з n символiв буде рiвна

Т = nt сек. (1.61)

Виключаючи n з формул (1.61) i (1.60), отримаємо

N = Ln = LT/t = LbT,(1. 62)

де b=1/t (символ/сек) являє собою швидкiсть передачi символiв по каналу. Таким чином, можливе число рiзноманiтних повiдомлень тривалостi Т росте зi збiльшенням T по експоненцiальному закону, що в функцiї часу справедливо i тодi, коли тривалiсть передачi окремих символiв неоднакова (але T >> ti).

При цьому вiн набуває вигляду

N(T)=AwT, (1. 63)

де А i w залежать вiд L i довжини символiв. Так, w визначається як найбiльший дiйсний корень рiвняння

(1.64)

де t1, t2, ..., tL - довжини символiв алфавiту.

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

Проiлюструємо сказане прикладом. Нехай за допомогою двiйкового цифрового коду потрiбно передати ординати електрокардiограмми з точнiстю до 1%. Яку довжину (скiльки розрядiв) двiйкового коду потрiбно взяти для цiєї мети? Оскiльки задана точнiсть 1%, то кiлькiсть рiзноманiтних повiдомлень (рiзноманiтних числових значень електрокардiограмми) буде N=100; L=2. Отже, n визначається з формули 100=2n, або найближче бiльше цiле n=7. Отже, для цифровой передачi електрокардiограмми зi згаданою точнiстю достатньо скористатися семирозрядним двiйковим кодом.

1.2 Коди з виявленням та виправленням помилок

1.2.1 Кодування інформації

Кодуванням називається процес встановлення певної вiдповiдностi мiж повiдомленнями i тiєю системою символiв, за допомогою яких цi повiдомлення передаються. Сама система символiв називається кодом.

Основнi цiлi кодування наступнi.

1. Надання повiдомленням максимально короткої (стислої) форми з метою збiльшення пропускної спроможностi каналу, зоокрема для кращого використання пам'ятi в математичних машинах.

2. Надання повiдомленням форми, зручної для подання їх за допомогою електричних або механiчних сигналiв.

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

4. Максимальна помiхостійкiсть лiнiї зв'язку i приладiв передачi i обробки iнформацiї.

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