Лекція 02. Дискретні та неперервні повідомлення. оцифровка
Курс “Теорія інформації та кодування”

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

Вступ. Зміст курсу ТІК та підходи до оцінювання
Дискретні на неперервні повідомлення
Підходи до оцифровки неперервних повідомлень
Квантування рівню інформаційного параметру
Дискретизація за часом

Вступ. Зміст курсу ТІК та підходи до оцінювання

Курс ТІК включає 16 лекцій та 8 лабораторний зайнять, на яких практично закріпляється вивчення теоретичного матеріалу. За результатами вивчання студент одержує залік. Зазвичай 2 лекції та відповідне лабораторне заняття утворюють тематичний блок. Матеріал курсу розділений на два близькі за обсягом навчальних модулі. Основні теми, порядок їх вивчання та розподіл по модулях відображені на рис.2.1.

Рисунок 2.1 Структура курсу ТІК

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

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

Сумарна оцінка за вивчення курсу (до 100 балів) складається із двох оцінок за модулі (відповідно 45 та 55 балів). Вона формується за підсумками вивчання тем №2-7 (до 15 балів за кожну шести цих тему), а також з урахуванням оцінки за вивчання тем 1 або 8 за вибором (до 10 балів).

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

Дискретні на неперервні повідомлення

Теорія інформації розділяє всі можливі форми повідомлень на два принципово різних види (рис.2.2):

Рисунок 2.2 Види повідомлень та їх співвідношення

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

- неперервні повідомлення (такі як зафіксовані значення фізичних величин, звук або природні статичні та динамічні зображення) можна представити як неперервні величини або їх залежності від часу та координат в просторі. Наприклад, температура, що зафікована датчиком, може мати будь-яке значення в певному інтервалі (подібно до розташування точки на відрізку лінії); звук можна представити як залежність тиску повітря від часу; статичне зображення — як залежність яскравості кольорів від координат на плоскості, а динамічне зображення — як неперервну зміну таких картинок-кадрів.

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

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

Водночас можливості перетворення дискретних повідомлень в неперервну форму обмежені.

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

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

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

Контрольні запитання
1) Наведіть приклади дискретних повідомлень
2) Наведіть приклади неперервних повідомлень
3) Чому саме дискретна форма повідомлень вважається універсальною
4) Укажіть основні переваги дискретної форми повідомлень


Підходи до оцифровки неперервних повідомлень

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

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

Рисунок 2.3 Приклади квантування одномірних неперервних величин

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

В нашому прикладі із вимірюваннем температури тіла висота стовпчику ртуті є неперервною величиною (вона може приймати будь-яке значення в певному діапазоні температур). Щоб представити таку величину числом в градусах, ми прив'язуємо її до одного з дискретних рівнів, що означений рискою на термометрі. Кількість цих рівнів визначається діапазоном неперервної величини (у випадку з термометром це зазвичай діапазон від 320С до 420С), а також відстанню між сусідніми рівнями (квантом або кроком квантування), що забезпечує достатню точність (тут — 0,10С). В нашому випадку кількість рівнів температури, яка може бути зареєстрована термометром складає (42-32)/0,1+1=101 (враховуючи, що кількість рівнів на 1 більша, ніж число інтервалів в діапазоні вимірювання).

Узагальнюючи, можна сказати, що результат вимірювання тут представляється одним знаком (довжина повідомлення L=1), який належить до алфавіту обсягом N=101. Форма представлення знаку залежить від задач кодування. Наприклад, звичним для сприйняття є десяткове представлення, отже знак може мати вигляд 38,9 (вочевидь тут форма знака є составною). При цьому з позицій інформації форма знаку не важлива: по суті він є лише посиланням на певний дискретний рівень температури. Щоб не пов'язувати його значення із конкретною формою, знак може задаватись просто відповідним номером в алфавіті (в даному випадку такий рівень температури буде мати номер (38,9-32,0)/0,1=69). Для збереженння в цифровому середовищі такий номер представляється в двійковій формі 1000101. До того ж із умов стандартизації довжина коду обирається кратною байту (8 двійкових розрядів). Отже на практиці такий код буде мати вигляд 01000101 — рис.2.3.

Двовимірна неперервна залежність (звуковий сигнал)
Другим прикладом буде оцифровка звука. Тут маємо залежність певного неперервного фізичного параметру (наприклад, електричної напруги u на виході мікрофону) від також неперервного часу t. Подібні повідомлення доречно називати двовимірними. Відзначимо, що математично неперервній функції u(t) еквівалентна будь-яка неперервна функція у(x), тобто її незалежним аргументом може бути не тільки час. Але на практиці залежності саме від часу розглядаються найчастіше. Приклад такої залежності наведений на рис.2.4.

Рисунок 2.4 Оцифрування двовимірної неперервної залежності (звуку)

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

Для оцифровки звуку результатом дискретизації за часом буде перехід від неперервної амплітуди звукової хвилі u(t) до послідовності фіксованих із певною частотою значень амплітуди u(i), а результатом квантування за рівнем — дискретні значення u*(i) амплітуд, які зазвичай кодуються в двійковій формі — рис.2.4.

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

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

В підсумку оцифроване двохвимірне повідомлення (зокрема звуковий фрагмент) має вигляд послідовності закодованих амплітуд. Кількість відліків амплітуди, які можна трактувати як знаки дискретного повідомлення становить L=Tmax/Δt, де Tmax — час звучання. Обсяг відповідного алфавіту визначається як для одномірних величин. Щоб відновити вихідну форму оцифрованого повідомлення до такої послідовності необхідно додати інформацію про довжину кодів амплітуд і частоту дискретизації. В комп'ютерній формі така інформація міститься в заголовку файлу повідомлення.

Трьохвимірна та чотирьохвимірна неперервні залежності (зображення та відео)
В третьому прикладі ми розглянемо оцифровку зображень — рис.2.5.
Оцифрування статичних зображень передбачає виділення матриці точок-пікселів (так званий растр). До двох вимірів растру додається третій вимір, який відповідає за кольори пікселів. Для створення динамічного зображення (зокрема відео) реалізується регулярна зміна статичних кадрів із заданою частотою. В цьому випадку час зміни кадрів стає четвертим виміром оцифрованого повідомлення.

Рисунок 2.5 Оцифрування статичних та динамічних зображень

На практиці при фото- або відео-з'ємці цифрове зображення створюється за рахунок того, що яскравість його ділянок, координати яких відповідають пікселям, фіксується світлочутивими елементами. У випадку сканування такі елементи групуються в лінійку, яка просувається вздовж зображення, поступово утворюючи растр. Габарити растра визначаються перш за все роздільною здатністю апаратури. Зокрема, типові нині значення габаритів біля 2000х3000 відповідають кількості пікселів 6 мільйонів (6 Мегапікселів).

Щодо кодування кольорів пікселів, для його розуміння наведемо спрощений приклад зображення із одним базовим кольором (наприклад — в градаціях сірого). Таке зображення створюється завдяки зміні яскравості пікселя від 0 (чорний колір) до максимального значення (білий колір). Зокрема, при довжині двійкового коду 1 байт (8 двійкових розрядів) можлива кількість градацій яскравості складає N=28=256. Цей параметр називають «глибиною кольору». Аналогічний підхід використовується для створення багатокольорових зображень за рахунок накладання яскравості трьох базових кольорів — червого, зеленого та синього (RGB). Надалі ми розглянемо цей механізм докладніше.

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

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

Контрольні запитанняя
1) Поясніть приклад оцифровки одновимірних неперервних величин, користуючись прикладом на рис.2.3.
2) Охарактеризуйте етапи дискретизації за часом та квантування за рівнем при оцифровці двовимірних неперервних повідомлень.
3) Які параметри необхідно додати до послідовності кодів амплітуд звуку, щоб адекватно відтворити вихідне звукове повідомлення.
4) Поясніть, які саме виміри маються на увазі, коли статичні та динамічні зображення трактуються відповідно як трьохвимірні та чотирьохвимірні.


Квантування рівню інформаційного параметру

Вибір розрядності коду рівнів квантування
Додатково упорядкуємо уявлення про вибір розрядності кодування квантованих рівнів неперервних величин — рис.2.6. При цьому використуємо числовий приклад.

Рисунок 2.6 До вибору розрядності кодування рівнів квантування

а) Нехай діапазон зміни неперервної величини u(t) складає від -4 до 4, а потрібна точність визначається квантом 0,02. Звідсіля потрібна кількість рівнів дискретизації відповідно формулі на рис.2.6 складає N(потр)=(4 -(-4))/0,02+1=401;

б) З іншого боку можлива кількість закодованих рівнів N(код) обмежується довжиною відповідного коду K. Зокрема для двійкового кодування N(код)=2K. Таким чином вибір довжини коду повинен враховувати умови N(код) >= N(потр). Для нашого прикладу мінімальне значення N(код), яке відповідає такій умові, складає 29=512. Відзначимо, що додавання кожного розряду коду здатне або розширити вдвічі діапазон параметру, або вдвічі зменшити крок квантування;

в) На практиці квантування неперервного параметру виконується стандартними мікросхемами аналого-цифрових перетворювачів — АЦП. Такі перетворювачі формують двійковий код, що відповідає рівню вхідного параметру (в формі напруги). При цьому поширені АЦП, які мають розрядність 8, 10, 12 або 16 (відповідно кількість рівнів 28=256, 210=1024, 212=4096, 216=65536). В нашому прикладі мінімальна розрядність АЦП - 10. Отже фактична кількість рівнів квантування N(факт)=1024, таким чином точність квантування може бути приблизно в 2,5 рази вищою, ніж мінімально допустима.

Використання міри децібел
Для багатьох фізичних параметрів, які підлягають квантуванню, використовується міра децибел. Зокрема, така міра широко застосовується для оцінювання гучності звуку. Отже, доцільно розглянути, як використання децибелів пов'язане із квантуванням — рис.2.7.

Базова формула для оцінювання в децибелах запропонована для так званих "енергетичних" величин (наприклад, для потужності та енергіїї, а по відношенню до звуку - для гучності). Вона має вигляд D = 10lgPx/P0, де Px — поточне значення параметру, а P0 - базове значення. Наприклад, гучність звуку 40дБ в 104 разів більше, ніж поріг чутливості слуху (10 lg104 = 40). Як можна бачити, зростання потужності в 10 разів тут відповідає збільшенню D на 10 дБ (відзначимо, що одиниця дБ безрозмірна). Оскільки енергетичні параметри сигналів (такі як потужність та енергія) пропорційні квадрату їх амплітуди U, то відповідна формула це враховує: D = 10lgPx/P0 = 10lgUx2/U02 = 20 lgUx/U0. Таким чином значення для амплітуди сигналу 40дБ відповідає амплітуді в 100 разів більшій, а також потужності (гучності звуку) в 10000 разів вищій, ніж поріг чутливості слуху — рис.2.7.

Рисунок 2.7 Визначення діапазону квантування в децібелах

Використання одиниці децибел дає низку важливих переваг. Так, логарифмічний масштаб забезпечує зручність роботи з великими значеннями (наприклад, замість того, щоб оцінювати звук, як в 1000000 раз гучніший в порівнянні з порогом чутливості, ми вкажемо, що його гучність D = 60дБ). Крім того, посилення і ослаблення сигналу тепер просто мають різний знак (наприклад, D = -10дБ означає, що потужність сигналу зменшена в 10 разів).

При квантуванні важливо визначити «ціну» одного двійкового розряду в дБ. Оскільки додавання кожного такого розряду збільшує діапазон відповідної величини вдвічі, то його ціна буде для енергетичних величин 10lg2=3 (дБ/розряд), а для амплітуд 20lg2=6 (дБ/розряд) — рис.2.7. Таким чином, наприклад, двійковий код довжиною 8 розрядів забезпечує динамічний діапазон амплітуди звуку 8х6=48 дБ, а для 16 розрядів 16х6=96 дБ. Саме таке значення можна зустріти в маркуванні цифрової звукової апаратури, де широко використовється 16-розрядне кодування. При цьому зазвичай тут вказується від'ємне значення, виходячи із максимально можливого рівня підсилення сигналу апаратурою.

Характеристики «шуму» квантування
При квантуванні зазвичай виникають похибки δu — відмінності вихідного неперервного значення величини u(i) відносно відповідного дискретного рівню u*(i) – рис.2.8. Такі похибки мають випадкові значення і зокрема звуться «шумом квантування». В практиці кількість інтервалів N є досить значною (десятки і більше). За таких умов розподіл плотності імовірності шуму квантування δu є близьким до рівномірного (рис.2.8).

Рисунок 2.8 Характеристики випадкових похибок («шуму») квантування

Зазвичай використовують один із двох підходів, який визначає характеристики шуму квантування: неперервне значення u(i) асоціюють із серединою інтервалу Δu, або з однією із його меж (наприклад нижньою). В першому випадку максимальне значення похибки квантування становить max(δu)=Δu/2 при середньому значенні m(δu)=0. В другому випадку max(δu)=Δu при m(δu)=Δu/2. При малих Δu різниця не є суттєвою. В практиці частіше використовується другий варіант більш простий в технічній реалізації. В обох випадках так зване стандартне відхилення (параметр розкиду) похибок δu визначається за формулою S(δu)=Δu/(2√3). Надалі ми використаємо ці формули в розгляді математичних моделей передачі інформації.

До цього моменту ми розглядали тільки варіант квантування з постійним кроком Δu. В деяких випадках здається доречним використання змінного рівню Δu. Наприклад, похибки в передачі звуку менше сприймаються на більш гучному фоні, отже можна було б зробити значення Δu пропорційним до амплітуди u(i) (подібні рішення колись дійсно практикувались). Але насправді простота технічної реализаціі АЦП із постійним кроком між рівнями має вирішальне значення. Саме такий спосіб застосовується нині повсюдно. Що ж до оптимізації сприйняття шуму кватнування, то вона реалізується програмно на подальших етапах обробки.

Контрольні запитання
1) Спираючись на рис.2.6, обгрунтуйте вибір розрядності кодів квантування для прикладу, коли діапазон вихідної величини складає від -5 до 5, а квант — 0,05.
2) Який діапазон в децибелах може забезпечити 12-розрядне кодування рівню напруги.
3) Розрахуйте значення стандартного відхилення шуму квантування, якщо довжина кванту складає 0,1.


Дискретизація за часом

Вибір частоти дискретизації. Правило Найквіста
Як ми уже знаємо, вибір частоти дискретизації визначає пропорцію між точністю оцифровки і обсягом коду. Принципово важливо, що існує така мінімальна частота дискретизації, для якої вихідну неперервну залежність можна відтворити без викоривлень. Саме її вибір вочевидь буде оптимальним.
Практичне правило вибору такої оптимальної частоти, що спирається на аналіз спектру сигналу для оцифрування, було запропоновано Гаррі Найквістом. Згідно цьому правилу частота дискретизації повинна бути вдівчі більшою, ніж максимальна частота вихідної неперервної залежності — (рис.2.9). Інакше кажучи, на кожний період максимальної частоти вихідного сигналу при дискретизації повинно приходитись як мінімум два відліки амплітуди. Для надійної практичної реалізації розрахункове значення fd зазвичай беруть із запасом в 10-15%.

Рисунок 2.9 Правило Найквіста для вибору частоти дискретизації

Класичним прикладом практичного використання правила Найквіста є дискретизація звуку. Зрозуміло, що для різних звукових повідомлень максимальна частота може суттєво різниться: порівняйте в уяві ревіння бика (fmax=30 Гц) та писк комара (fmax=10000 Гц). Однак спільною точкою “відліку” тут є обмеження слуху людини. Досить приблизно вважають, що людське вухо не сприймає частоти заввишки fmax=20000 Гц = 20 кГц. Відсіль згідно правилу Найквіста та з урахуванням запасу в 10% маємо fd=2х20х1,1 = 44 кГц. Саме таку частоту дискретизації звуку найчастіше використовують в практиці.

Теорема Котельнікова про вибір частоти дискретизації
Математичне обгрунтування вибора частоти дискретизації було запропоновано радянським вченим Володимиром Котельниковим. Зокрема, згідно теоремі Котельникова будь-яка неперервна залежність u(t) може бути відновлена без втрат інформації по своїм дискретним відлікам u(i) з використанням формули, що наведена на рис.2.10.

Рисунок 2.10 Використання формули Котельнікова

Аналіз формули Котельникова (рис.2.10) показує, що вихідна залежність u(t) тут відновлюється підсумовуванням дискретних відліків, взятих з кроком дискретизації Δt, кожен з яких множиться на спеціальну коливальну функцію (функцію Котельнікова). В результаті може бути отримана згладжена залежність, що повністю збігається із вихідною.

Разом з тим, формула показує і обмеження такого підходу: підсумовування має вестися на нескінченній множині відліків, при цьому "хвости" коливальних функцій також поширюються в нескінченність. Буквально це реалізувати неможливо. На практиці до цього додається складність технічної реалізації «ідеальних» функцій Котельникова.

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

Контрольні запитання
1) Визначте частоту дискретизації згідно правилу найквіста, якщо максимальна частота, що міститься у вихідній неперервній залежності, складає 10 кГц.
2) Зформулюйте теорему Котельнікова про вибір частоти дискретизації, спираючись на рис.2.10.
3) Чому саме при визначенні частоти дискретизації за правилом Найквіста на практиці потрібно враховувати 10-15%-ний запас.

О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2019 • Теория информации и кодирования
UP