5.4 Кодування дискретних повідомлень

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

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

Дискретне повідомлення складається з кінцевого числа символів. Кожний символ, що може зустрічатися в повідомленні, можна пронумерувати, тоді текст повідомлення можна подати як послідовність чисел – номерів символів у списку. (Приклад «баба» ~ «02010201»)

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

B=b₁,b₂,…,b_i,…,b_N,

де N – загальна кількість різних символів b_i, які можуть зустрічатися в повідомленні.

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

B=а,б,в,…,А,Б,В,…,0,1,2,…,+,–,*,/.

Кожний символ повідомлення b_i можна записати за допомогою деяких інших кодових символів (цифр) , які утворюють собою алфавіт A.

Алфавіт – це множина кодових символів , за допомогою яких кодуються символи повідомлення b_i.

,

де m – загальна кількість кодових символів (цифр) алфавіту A.

Загальна кількість m кодових символів алфавіту A називається основою коду.

Алфавіти відмінні між собою загальною кількістю кодових символів.

Наприклад:

A₂ – двійковий алфавіт: A₂=0,1, m =2,

A₈ – вісімковий алфавіт: A₈=0,1,2,…,7, m =8,

A₁₀ – десятковий алфавіт: A₁₀=0,1,2,…,9, m =10,

A₁₆ – шістнадцятковий алфавіт: A₁₆=0,1,2,…,9,A,B,C,D,E,F, m =16.

З символів алфавіту A можна складати кодові слова або кодові комбінації:

,

де n – довжина кодового слова К.

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

Приклад:

n=5, A₂ , K=01101₂ – кодове слово записано у вигляді 5–розрядної кодової комбінації за допомогою двійкового алфавіту, m =2.

n=5, A₁₆, K=51F0E₁₆, m =16.

n=5, A₁₀, K=93615₁₀, m =10.

В кодовому слові n біт (розрядів), в алфавіті – m символів (цифр).

Скільки різних слів довжиною можна записати за допомогою алфавіту A з основою коду m?



n раз

де N₀ – загальна кількість кодових слів K.

Приклад: скільки різних 8–розрядних кодових слів можна скласти за допомогою двійкового алфавіту?

m =2, n =8, N₀=2⁸=256 слів,

де m – основа коду,

n – довжина кодового слова.

За допомогою алфавіту A₁₆ можна скласти N₀=16²=256 двохбітових кодових слів.

Для кодування повідомлень довжиною n символів, треба щоб загальна кількість кодових слів N₀ була б не менше за кількість кодових слів, які використовуються для кодування всіх можливих символів повідомлення N.

Тобто потрібно щоб завжди виконувалася умова:

N ≤ N₀.

Приклад:

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

,

тобто

~ , .

Загальний список кодових слів K_i називається кодом. В списку може бути не більше кодових слів.

Перетворювання повідомлень з однієї форми в іншу за допомогою коду називається кодуванням повідомлення.

Кодове слово K_i можна розглядати як n-розрядне число в системі числення з основою m:

.

Наприклад: K=01101₂ можна розглядати як 5-розрядне двійкове число.

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

При фізичному опрацюванні даних на ЕОМ використовується двійкове кодування чисел (фізично 0 – немає імпульсу, 1 – є). З цими імпульсами оперують ЕОМ.