5.5 Способи перетворювання кодів

Перетворення цілих чисел K з однієї системи числення з основою m в іншу систему числення з основою М можна робити наступними способами.

1-й спосіб. Ділення числа K на М за допомогою арифметики з основою . Цифрами числа K в системі числення з основою М будуть залишки від ділення. Зручно користуватися цим способом при переведенні з десяткової системи числення (m=10), тому, що використовується десяткова арифметика.

Наприклад: К=71₁₀; 108.

71/8 = 8 залишок 7 = а_о; 8/8 = 1 залишок 0 = а₁; 1/8=0 залишок 1 = а_{2 .}  К=107₈.

2-й спосіб. Множення цифр числа К на степені за допомогою арифметики основи М, тобто обчислення значення багаточлена:

.

Зручно користуватися при переведенні в десяткову систему числення з інших систем (використовується десяткова арифметика).

Наприклад: К=1000111₂; 210.

К=2⁶+2²+2¹+2⁰=71₁₀.

3-й спосіб. Легко перетворювати числа із системи числення з основою у систему числення з основою М=2^Р і навпаки. (Зрозуміло, якщо Р=3, то це вісімкова система числення; якщо Р=4, то це шістнадцяткова система числення. Вони використовуються при опрацюванні даних на ЕОМ.) Для цього потрібно запам’ятати таблиці двійкового запису вісімкових і шістнадцяткових цифр (табл. 31).

Таблиця 31 – Двійкові коди вісімкових та шістнадцяткових цифр

цифра	двійковий запис	цифра	двійковий запис
0	0 000	8	1000
1	0 001	9	1001
2	0 010	A(10)	1010
3	0 011	B(11)	1011
4	0 100	C(12)	1100
5	0 101	D(13)	1101
6	0 110	E(14)	1110
7	0 111	F(15)	1111

Для перетворення необхідно об’єднати відповідним чином розряди двійкового числа.

Наприклад: 47₁₆=0100 0111₂; 001 000 111₂=107₈.

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

5.6 Ентропія як міра кількості інформації

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

При цьому абстрагуються від змісту цієї інформації.

Приклад.

Нехай система S має 4 стани з ймовірностями P₁=0,5; P₂=0,25; P₃=P₄=0,125. Для передачі повідомлення про стан системи S можна скористатися рівномірним двохбітовим кодом:

S₁ ~00; S₂~01; S₃~10; S₄~11.

Щоб передавати за секунду 1000 повідомлень про стан системи S треба мати канал зв’язку потужністю 2000 біт за секунду (бод).

Розрахуємо ентропію системи S:

Як бачимо, для з’ясування стану системи S достатньо в повідомленні передавати в середньому всього 1.75 біт інформації, а не 2 біта, як ми припускали при використанні рівномірного двохбітового коду.

Часткова інформація в кожному окремому повідомленні про стан системи S є різною і дорівнює:

• в 1-му стані: біт,

• в 2-му стан: біта,

– в 3-му чи 4-му стані: біта.

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

У відповідності до отриманих даних про часткову інформацію в окремих повідомленнях про стан системи складемо коди для їхньої передачі інакше:

S₁~0(1 біт); S₂~10(2 біта); S₃~110(3 біта); S₄~111(3 біта).

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

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

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

Алгоритм розпізнавання змісту повідомлення: якщо перший символ 0, то це S₁ (і кінець), інакше, якщо другий символ 0, це S₂ (і кінець), інакше, якщо третій символ 0, це S₃ (і кінець), інакше це S₄.

Відшукаємо середню кількість інформації в повідомленнях про стан системи S, закодованих префіксним кодом:

біт.

де – кількість біт в окремому повідомленні про стан системи .

Відповідно для передачі повідомлень про стан системи S за одну секунду префіксним кодом треба мати канал зв’язку потужністю 1750 біт за секунду (бод), а не 2000, як при використанні рівномірного коду.

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

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

Якщо б всі стани системи були б рівноймовірні, то користуватися префіксним кодом було б недоречно. Доведемо це.

Розрахуємо ентропію системи Z з чотирма рівноймовірними станами:

біта,

Середня кількість інформації в повідомленнях про стан системи Z, закодованих префіксним кодом:

біт.

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

біта.

Таким чином для кодування повідомлень про стан системи Z треба скористатися рівномірним кодом. Рівність ентропії системи Z та повної інформації в повідомленнях про її стан є ознакою оптимального кодування повідомлень.

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

Саме так складають оптимальні коди повідомлень, а також розраховують потужність каналів зв’язку та запам’ятовуючих пристроїв.