Системи числення

Елементи теорії кодування

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

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

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

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

Системи числення

Методика побудови кодів тісно пов’язана з відповідними системами числення. Побудова системи числення залежить від її основи, тобто кількості цифр, з яких можна одержати будь -яке число.

Так, десяткова система базується на цифрах від 0 до 9, двійкова - 0 та 1, вісімкова - від 0 до 7, шістнадцяткова - на цифрах від 0 до 9 та літерах A, B, C, D, E, F. В таблиці 9.1 наведено співвідношення чисел у різних системах числення.

Таблиця1 - Співвідношення чисел

Десяткова	Двійкова	Вісімкова	Шістнадцяткова
			0A
			0B
			0C
			0D
			0E
			0F

 

Кодування інформації методом Шеннона

 

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

Характеристиками коду є значність і його основа. Значность коду n - число символів в кодовому слові (кодової комбінації), а основа L - число різних символів коду. Найбільш розповсюджені двійкові (бінарні) коди з основою L = 2. Рівномірним є такий код, у якого значність коду для всіх кодових слів однакова (наприклад, код Бодо).

При кодуванні повідомлень, переданих каналами зв'язку без перешкод, необхідно виконати дві умови:

1. кодові слова мають бути розрінювані і однозначно пов'язані з відповідними повідомленнями;

2. застосовуваний спосіб кодування повинен забезпечити максимальну економічність (стислість) коду, при якій на передачу даного повідомлення витрачається мінімальний час.

Код, що задовольняє другу з цих умов, називається оптимальним.

Якщо x = { x_i }, i = 1, 2,..., N - ансамбль взаємно незалежних повідомлень з апріорними ймовірностями p (x_i), a y = { y_k }, k = 1, 2,..., L - ансамбль символів коду L <N, то число кодових слів по n символів в кожному слові M = L_n.

При L_n ≥ N, де n - найменше ціле число, для якого виконується ця нерівність.

Приклад 1Закодувати за методом Шеннона - Фено повідомлення з N = 24 символів:

математика_ - _царица_наук

Рішення. Випишемо в таблицю частоти n_i та ймовірності p_i = появи кожної букви повідомлення

 

 

x М А Т Е И К Ц Р Н У _ -

n 2 6 2 1 2 2 2 1 1 1 3 1

p 0.08 0.25 0.08 0.04 0.08 0.08 0.08 0.04 0.04 0.04 0.15 0.04

 

Знайдемо ентропію повідомлення

-H (x) = pi ln pi =+ 0.08 · ln 0.08 + 0.08 · ln 0.08 + 0.08 · ln 0.08 + 0.04 · ln 0.04 + 0.04 · ln 0.04 +

=+0.08 · ln 0.08 + 0.25 ln 0.25 + 0.08ln 0.08 + 0.04 · ln 0.04 ++ 0.04 · ln 0.04 + 0.15 · ln 0.15 + 0.04 · ln 0.04 ∼ 3.3.

 

Розташуємо символи в порядку спадання ймовірностей:

 

x А _ Ц К И М Т Е Р Н У -

p 0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04

 

Розіб'ємо таблицю на дві групи таким чином, щоб сума ймовірностей появлення символів в кожній групі була приблизно однаковою. Помітимо всі букви потрапили в першу групу символом 0, а всі букви потрапили в другу групу символом 1.

 

0,44	0.56
А	_	Ц	К	И	М	Т	Е	Р	Н	У	-
0,25	0,15	0,08	0,08	0,08	0,08	0,08	0,04	0,04	0,04	0,04	0,04

 

Аналогічно, розбиваємо першу групу на дві рівні за ймовірностями частини і при-

привласнювати першій групі символ 0, а другій групі - символ 1 і.т.д.

А	_	Ц	К	И	М	Т	Е	Р	Н	У	-
0,25	0,15	0,08	0,08	0,08	0,08	0,08	0,04	0,04	0,04	0,04	0,04

 

Об'єднуючи символи для кожної букви отримаємо кодову таблицю

А		И		Р
_		М		Н
Ц		Т		У
К		Е		-

 

Економність коду - кількість інформації, що припадає на один кодовий символ, обчислюється як відношення ентропії алфавіту до математичного очікування довжини кодового позначення букв повідомлення. У нашому випадку буквах повідомлення відповідають коди довжиною 3 символу для букв (А, _, І, М) і 4 символу - для решти 8-ми букв. Розподіл ймовірностей появи коду даної довжини дано в таблиці

п
_р	1/3	2/3

Таким чином, математичне очікування довжини закодованої літери є

М(п) = 3*1/3 + 4*2/3 = 3.67

Для економності коду

S= H (x)/ М(п) = 3.3/3.67=0.899.

Оптимальним називається код, в якому середня довжина кодового слова дорівнює

ентропії, тобто S = 1.

 

Елементи двійкової арифметики

 

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

Розглянемо найпростіше поле з двох елементів 0 і 1. Визначимо для нього операції додавання і множення так:

0+0=0, 0+1=1, 1+0=1, 1+1=0;

0*0=0, 0*1=0, 1*0=0, 1*1=1.

Визначені таким чином операції додавання та множення називають додаванням та множенням за модулем 2 (mod 2). Операція додавання за mod 2, як правило, позначається символом Å

Наприклад, 0101101

⊕1001010

 

Завадонезахищені коди

 

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

Коди зведені до таблиці 9.2.

Символ	Двій- ковий	Код Грея	ASCII
			31 30
			31 31
			31 32
			31 33
			31 34
			31 35

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

число комбінацій: N = 2ⁿ,

де n - максимальна кількість розрядів.

У двійковому коді деякі кодові комбінації, що розташовані поряд розрі з- няються декількома розрядами. Таким чином, у випадку зчитування може виникнути велика похибка (0111 - 1000). Для уникнен ня цього використовують коди, в яких, при переході від одного числа до іншого,

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

 

Код Грея називають відбитим (рефлексним) і викорис товують для виготовлення кодувальних дисків та кодувальних масок.

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

Код ASCII використовується у комп’ютерній техніці і базується на шістнадцятковій системі числення. Кожному з символів відповідає дв о- значний десятковий код.

 

Коди з визначенням та виправленням помилок

Идея помехоустойчивого кодирования заключается в добавлении к сообщению лишних символов, помогающих заметить ошибку. Теперь множество кодовых комбинаций увеличивается и состоит из двух подмножеств:

- разрешенных комбинаций и

- запрещенных комбинаций

Для того чтобы обнаруживать и исправлять ошибки, разрешенная комбинация

должна как можно больше отличаться от запрещенной. Расстоянием между двумя комбинациями называется количество разрядов, которыми они отличаются (количеством единиц). Например расстояние между буквами "m" (1101101) и "o" (1101111) будет 1. Расстояние между "a" (1100001) и "z" (1111010) будет 4. Весом комбинации называется количество в ней единиц. Очевидно что вес - это расстояние от нулевой комбинации (00000).

Поскольку сумма комбинаций есть другая комбинация, то по аналогии с векторной алгеброй можно вычислять расстояние между комбинациями как вес их суммы (по модулю 2: ⊕).

 

Коригувальна здатність коду залежить в ід кодової відстані:

 при d = 1 помилка не виявляється;

 при d = 2 виявляються поодинокі помилки;

· при d = 3 виправляються поодинокі помилки або виявляються подвійні помилки.

У загальному випадку:

d = r + s + 1,

де r - кількість помилок, що виявляються;

s - кількість помилок, що виправляються.

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

Для кодування за алгоритмом Хеммінга у вигляді початкового б еруть двійковий код на всі сполучення з додаванням контрольних символів. Для одного інформаційного символу потрібно 2 контрольних, для двох - 3, для п’яти - 4, для дванадцяти - 5.

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

k 4 k 3 k 2 m 3 k 1 m 2 m 1; (9.3)

де k - інформаційні символи;

m - перевірочні (контрольні) символи.

Контрольні символи формуються додаванням за модулем 2 інфо р- маційних розрядів:

Выпишем таблицу истинности для трех проверочных разрядов. Обозначим информационные разряды символом bi, а проверочные символом ai. Тогда, проверочные разряды восстанавливаютсяпо информационным по следующим правилам:

Таблиця - Перевірочна таблиця коду Хеммінга

m 3	m 2	m 1	Символи
			m1	т 1 = к1 ⊕ к2 ⊕ к4 т 1 = к1 ⊕ к3 ⊕ к4   т 2 = к2 ⊕ к3 ⊕ к4
			m 2
			k 1
			m 3
			k 2
			k 3
			k 4

Т.е. значение a0 формируется из всех к_k для которых т ₁= 1. Значение k ₂ форми-

руется из всех k ₂ для которых т ₁ = 1, и т.д. На передатчик канала связи подается

самокорректирующийся код Хэмминга [7, 4], который имеет вид

 

(т ₁, т ₂, к1, т ₃, к2, к3, к4

На приемном конце канала связи для проверочных символов строится аналогичная

комбинация:

A0 = b1 ⊕ b2 ⊕ b4

A1 = b1 ⊕ b3 ⊕ b4

A2 = b2 ⊕ b3 ⊕ b4

Разница между передаваемыми ai и принимаемыми Ai проверочными разрядами поз-

воляет обнаружить и локализовать ошибку. Место ошибки определяется формулой

M = 20 · (a0 ⊕ A0) + 21 · (a1 ⊕ A1) + 22 · (a2 ⊕ A2).

 

Пример 3.1 Построить по методу Хэмминга кодовое слово для сообщения (1010).

Решение. Зная количество информационных символов k = 4 сообщения, найдем

количество проверочных символов из формулы

 

2r ≥ k + r + 1, или 23 = 8 ≥ 4 + 3 + 1 = 8,

т.е. n = k + r = 4 + 3 = 7. Поскольку r = 3, то для передаваемой последовательности

кода [n, k] = [7, 4] будем иметь (a0, a1, b1, a2, b2, b3, b4). Учитывая, что

(b1, b2, b3, b4) = (1010),

для проверочных символов получим

 

a0 = b1 ⊕ b2 ⊕ b4 = 1 ⊕ 0 ⊕ 0 = 1

a1 = b1 ⊕ b3 ⊕ b4 = 1 ⊕ 1 ⊕ 0 = 0

a2 = b2 ⊕ b3 ⊕ b4 = 0 ⊕ 1 ⊕ 0 = 1

Передаваемое кодовое слово имеет вид

(a0, a1, b1, a2, b2, b3, b4) = (1011010).

 

Пример 3.2. На приемнике было получено кодовое слово (0101101) построенное

по методу Хэмминга. Восстановить исходное сообщение.

Решение. Полученное кодовое слово имеет вид

(a0, a1, b1, a2, b2, b3, b4) = (1101101).

Учитывая, что здесь b1 = 0, b2 = 1, b3 = 0, b4 = 1 для проверочных символов получим

 

A0 = b1 ⊕ b2 ⊕ b4 = 0 ⊕ 1 ⊕ 1 = 0

A1 = b1 ⊕ b3 ⊕ b4 = 0 ⊕ 0 ⊕ 1 = 1

A2 = b2 ⊕ b3 ⊕ b4 = 1 ⊕ 0 ⊕ 1 = 0

Разница между передаваемыми ai и принимаемыми Ai проверочными разрядами

дает место ошибки определяемой формулой

M = 20 · (a0 ⊕ A0) + 21 · (a1 ⊕ A1) + 22 · (a2 ⊕ A2)

= 20 · (1 ⊕ 0) + 21 · (1 ⊕ 1) + 22 · (1 ⊕ 0)

= 20 · 1 + 21 · 0 + 22 · 1 = 5.

Отсчитывая слева направо 5-й разряд в комбинации (1101101) и меняя его на про-

тивоположный, получим

(1101101) → (1101001).

Теперь выделяя информационные символы, восстановим сообщение

b1 = 0, b2 = 0, b3 = 0, b4 = 1, или (0001).