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

З (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 (a_i) = 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(a_i) = n log L           (1. 55)

ⁱ⁼¹

Вираз (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(a₁, ..., a_n). Такий код буде волод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(a₁, ..., a₄) = 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 = -log¹/₂=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нчиться трьома результатами: А₁ - буде поставлений правильний дiагноз, A₂ - дiагноз не буде поставлений, А₃ - д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домлення S_i по вiдношенню до певного результату дiяльностi A_j будемо розумiти по аналогiї з (1.17)

.      (1.57)

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

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

C(S_i, a) =H(a) - Hs_i(a).     (1. 58)

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

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=Lⁿ        (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вна Lⁿ. Додамо до цiєї послiдовностi ще один символ. Тодi, підставляючи на це нове мiсце будь-який з L символiв, отримаємо з кожного старого повiдомлення L нових повiдомлень. Всього кiлькiсть нових повiдомлень буде рiвна

N_n+1 = Lⁿ  · L = Lⁿ⁺¹ ,

тобто ми довели, що якщо вираз (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 = Lⁿ = L^T/t = L^bT,     (1. 62)

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

N(T)=Aw^T,       (1. 63)

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

                          (1. 64)

де t₁, t₂, ..., t_L - довжини символiв алфавiту.

Експоненціальнiй закон  збiльшення числа повiдомлень  справедливий i тодi, коли в код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=2ⁿ, або найближче бiльше цiле n=7. Отже, для цифровой передачi електрокардiограмми зi згаданою точнiстю достатньо скористатися семирозрядним двiйковим кодом.

 

 

3. КОДИ З ВИЯВЛЕННЯМ ТА ВИПРАВЛЕННЯМ ПОМИЛОК

 

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нший.

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