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

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

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

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

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

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

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

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

Так,десятковасистемабазуєтьсянацифрахвід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), ay = { 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) = p_ilnp_i=+ 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.080.08 0.08 0.08 0.04 0.04 0.04 0.040.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).