2025: Комп'ютерні системи і мережі. Кодування даних в мережах.

• 2025: Комп'ютерні системи і мережі. Кодування даних в мережах.
• Завдання кодування даних в мережах
• Кодування джерела інформації
  • Кодування з повними даними про ймовірносний розподіл.
    • Функція Хартлі
    • Iнформаційна ентропія Шеннона
    • Взаємна інформація
    • Крокова пропускна спроможність ймовірнiсного каналу зв'язку
• Пропускна спроможність фізичного каналу з енергією сигналу та шумами
• Алгоритми кодування потоків даних
  • Кодування Хаффмана
  • Алгоритм кодування LZW
    • Кодування
    • Декодування
    • Схема використання в мережах
• Завдання
• Ресурси

Завдання кодування даних в мережах

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

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

• Сама назва "стиснення інформації", незважаючи на те, що воно повсюдно використовується, є дезінформацією. Поясніть чому?

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

Для немережевих додатків можно так розділити методи "стиснення":

1. "Стиснення" без втрат — можливо відновлення вихідних даних без пошкоджень.
2. "Стиснення" зі втратами — відновлення можливе з незначними пошкодженнями.

Але для мережних додатків можна розробляти протоколи та алгоритми, для яких межа між цими видами "стиснення" може стати важкорозрізненою.

• Які підходи до створення протоколів прикладного рівня можуть призвести до злиття цих двох класів "стиснення" даних?

Кодування джерела інформації

Кодування з повними даними про ймовірносний розподіл.

Функція Хартлі

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

$\mathcal{A}$ (алфавіту), міра інформації на один елемент множини (алфавіту) надається функцією Хартлі:

$${\displaystyle H_0(\mathcal{A}):={\log }_b|\mathcal{A}|,}$$
де

$|A|$ позначає потужність множини (алфавіту)

$A$, а основа логарифма

$b$ визначає метод кодування.

• Що означає ця ілюстрація?

• Чому це міра інформації на один елемент множини (алфавіту)?

Якщо основа логарифма

$b$ дорівнює 2, то одиницею невизначеності є біт. Якщо

$b$ - це основа експоненційної функції

$e^x$ то одиницею є нат. Хартлі використовував логарифм за основою 10, і з цією основою одиниця інформації називається хартлі (або діт) на його честь.

$H_0$ також відома як ентропія Хартлі або максимальна ентропія.

• Що таке

  $H_1$?

• Який вид (алгоритм) кодування елементів множини

  $\mathcal{A}$ ви можете запропонувати для
  $b=2$? Для яких розмірів множини
  $\mathcal{A}$ він максимально ефективний?

• Який вид (алгоритм) кодування елементів множини

  $\mathcal{A}$ ви можете запропонувати для
  $b=10$? Для яких розмірів множини
  $\mathcal{A}$ він максимально ефективний?

• Який вид (алгоритм) кодування елементів множини

  $\mathcal{A}$ ви можете запропонувати для
  $b=e=2.718281828....$? Для яких розмірів множини
  $\mathcal{A}$ він максимально ефективний?

• Яка міра інформації (невизначеність) об'єднання множини

  $\mathcal{A}$ із собою ?
  
  $${\displaystyle H_0(\mathcal{A}\cup \mathcal{A}):=?}$$

• Яка міра інформації (невизначеність) декартового добутку двох скінченних множин

  $\mathcal{A}$ і
  $\mathcal{B}$ ?
  
  $${\displaystyle H_0(\mathcal{A}\times \mathcal{B}):=?}$$

• Обчислите ентропію Хартлі для

  $\mathcal{A}=\{a,b,c,d\}$

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

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

1. джерело даних
2. канал зв'язку
3. приймач

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

Eнтропія

$H(X)$ дискретної випадкової змінної

$X$ (ентропія Шеннона) - це середній рівень «інформації», «сюрпризу» або «невизначеності», притаманний можливим результатам змінної

$X$.
Нехай дано дискретну випадкову величину

${\displaystyle X}$, яка приймає значення в алфавіті

${\displaystyle \mathcal{X}}$ і розподіляється відповідно до розподілу ймовірностей

${\displaystyle p:\mathcal{X}\to [0,1]}$. Тоді ентропія

$H$ випадкової величини

${\displaystyle X}$ дорівнює

$${\displaystyle \mathrm{H}(X):=-\sum _{x\in \mathcal{X}}p(x)\log p(x),}$$
де оператор

${\displaystyle \sum _{x\in \mathcal{X}}}$ позначає суму можливих значень змінної

${\displaystyle X}$.

• Обчислите ентропію Шеннона для

  $\mathcal{X}=\{a,b,c,d\}$, де
  $p(a)=1/2$,
  $p(b)=1/4$,
  $p(c)=1/8$,
  $p(d)=1/8$

• Який обсяг інформації буде передано в середньому у повідомленні довжиною 100 символів з даного алфавіта з указаним розподілом вірогідності символів?

• Чому з мерою Шеннона можна говорити тільки про середнє значення передаваної інформації?

Взаємна інформація

На основі ентропії Шеннона можна ввести величину, яка називається взаємною інформацією двох множин

$\mathcal{X}$ та

$\mathcal{Y}$ , пов'язаних розподілом ймовірності

$p(x,y)$ (наприклад, обумовленої характеристиками каналу зв'язку):

$$I(\mathcal{X},\mathcal{Y})=\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$$

• Чому дорівнює взаємна інформація

  $I(\mathcal{X},\mathcal{X})?$

• Як би Ви назвали величину

  $\frac{p(x,y)}{p(x)p(y)}$?

Крокова пропускна спроможність ймовірнiсного каналу зв'язку

На основі взаємної інформації двох множин

$\mathcal{X}$ (що є входом до ймовірнiсного каналу зв'язку) та

$\mathcal{Y}$ (що є виходом каналу зв'язку) можна ввести величину, яка називається крокова пропускна спроможність

$\mathcal{C}$ ймовірнiсного каналу зв'язку :

$$\mathcal{C}=\underset{p_X(x)}{sup}I(X,Y)$$

• Яким має бути розподіл

  $p_X(x)$, щоб максимізувати цю величину?

• Як цей розподіл може допомогти при розробці алгоритмів "стиснення" даних?

• Як цей розподіл може допомогти при розробці алгоритмів захисту даних?

Пропускна спроможність фізичного каналу з енергією сигналу та шумами

Нехай нам дана

$B$ - спектральна ширина каналу (Hz),

$E$ – енергія джерела сигналу,

$N$ - енергія шумів у каналі.
Тоді пропускна здатність фізичного каналу з енергією сигналу та шумами:

$$C=B\log (1+\frac{E}{N}),$$
де

${\displaystyle C}$ — пропускна здатність каналу в бітах на секунду – теоретична верхня межа чистої швидкості передачі даних.

• Як ця формула визначає розвиток комп'ютерних мереж?

Алгоритми кодування потоків даних

Кодування Хаффмана

У інформатиці та теорії інформації код Хаффмана — це особливий тип оптимального префіксного коду, який зазвичай використовується для стиснення даних без втрат. Процес пошуку або використання такого коду є кодуванням Хаффмана, алгоритмом, розробленим Девідом А. Хаффманом, коли він був студентом Массачусетського технологічного інституту та опублікований у статті 1952 року "A Method for the Construction of Minimum-Redundancy Codes".
Вихідні дані алгоритму Хаффмана можна розглядати як кодову таблицю змінної довжини для кодування вихідного символу (наприклад, символу у файлі). Алгоритм отримує цю таблицю з оціненої ймовірності або частоти появи (ваги) для кожного можливого значення вихідного символу. Як і в інших методах ентропійного кодування, більш поширені символи, як правило, представлені за допомогою меншої кількості бітів, ніж менш поширені символи. Метод Хаффмана може бути ефективно реалізований, знаходячи код за час, лінійний кількості вагових коефіцієнтів, якщо ці ваги відсортовані.

Іллюстрація побудови дерева Хаффмана

Алгоритм кодування LZW

(LZW) — це універсальний алгоритм стиснення даних без втрат, створений Абрахамом Лемпелем, Джейкобом Зівом і Террі Велчем. Він був опублікований Уелчем у 1984 році як вдосконалена реалізація алгоритму LZ78, опублікованого Лемпелем і Зівом у 1978 році. Алгоритм простий у реалізації та має потенціал для дуже високої пропускної здатності в апаратних реалізаціях.

Кодування

Загальний вигляд алгоритму кодування:

1. Ініціалізувати словник, щоб він містив усі рядки довжиною один.
2. Знаходження у словнику найдовшего слова W, яке відповідає префіксу поточного введеного рядка.
3. Видавання словникового індексу слова W як кода та видалення префікса W із введенного рядка.
4. Конкатенація слова W і наступного символу та додавання результату до словника.
5. Переход до кроку 2.

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

Декодування

Загальний вигляд алгоритму декодування:

1. Ініціалізуйте словник, щоб він містив усі слова довжиною один символ.
2. Прочитайте наступний код (закодований символ):
   чи він закодований у словнику?
   Так:
   1. Вивести відповідний рядок W на вихід.
   2. Об’єднайте попередній рядок, виданий для виведення, з першим символом W. Додайте це до словника.
   Ні:
   1. Об’єднує попередній рядок, виданий для виведення, з його першим символом. Назвіть цей рядок V.
   2. Додайте V до словника та виведіть V для виведення.
3. Повторюйте крок 2 до кінця рядка введення

Алгоритм декодування працює шляхом зчитування значення із закодованого введення та виведення відповідного рядка зі словника. Однак повний словник не потрібен, лише початковий словник, який містить односимвольні рядки. Натомість повний словник перебудовується під час процесу декодування: після декодування значення та виведення рядка декодер об’єднує його з першим символом наступного декодованого рядка.

Наприклад, для текстів з малих латинських літер початковий словник може бути таким:

Symbol	Binary	Decimal
'#'	00000	0
A	00001	1
B	00010	2
C	00011	3
D	00100	4
E	00101	5
F	00110	6
G	00111	7
H	01000	8
I	01001	9
J	01010	10
K	01011	11
L	01100	12
M	01101	13
N	01110	14
O	01111	15
P	10000	16
Q	10001	17
R	10010	18
S	10011	19
T	10100	20
U	10101	21
V	10110	22
W	10111	23
X	11000	24
Y	11001	25
Z	11010	26

Схема використання в мережах

Завдання

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

$S_X$, а друга – вихідна

$S_Y$ ймовірнiсного каналу

$S_X\to S_Y$ .
Наприклад,

Sx: anastasialarina2003anastasialarina2003anastasialarina2003.....
Sy: arthurmaximov1964arthurmaximov1964arthurmaximov1964...........
 

1. Підрахувати ентропії
   $H_0$ і
   $H$ та об'єми інформації в першій послідовності
   $S_X$ та в другій
   $S_Y$ з урахуванням частот
   $p_X$ та
   $p_Y$ (ймовірностей) символів в послідовностях.
2. За цими двома рядками потрібно підрахувати матрицю
   $p(x,y)$
3. Підрахувати взаємну інформацію
   $I(X,Y)$ для множин символів вхідної послідовністі
   $S_X$ у каналі та – вихідної
   $S_Y$.
4. Отримати значення крокової пропускної спроможність
   $\mathcal{C}$ ймовірнiсного каналу зв'язку
   $S_X\to S_Y$ .
5. Для рівня шумів
   $N={10}^{-3}\text{Wt}$, спектральної ширини каналу
   $В=1\text{Hz}$ і пропускної здатності
   $C=100\text{bit/sec}$ підрахувати потужність
   $E$ сигналу в каналі.
6. Зробити висновки про принципи побудови енергетично ефективних каналів та мереж.
7. Закодувати тексти алгоритмом Хафмана
8. Закодувати тексти алгоритмом LZW
9. Порівняти довжину кодів з об'ємами інформації, базованими на ентропіях Хартлі та Шенона. Зробити висновки

Ресурси