Елементи теорії кодування
Код –множинакомбінаційвдеякомуалфавіті,поставленаувзаємнооднозначнувідповідність зпочатковоюмножиною.
Кодування –встановленнявідповідностіміжелементомпочатковихданих і кінцевоюсукупністюсимволів,щоназиваєтьсякодовоюкомбінацією.
Взалежностівідкількостіознакпосиланькодуваннябуваєодноелементнимтабагатоелементним. Одноелементнекодування відбуваєтьсянаосновіоднієїознакипосилання(полярність,амплітуда,частота, три-валість, фаза), а багатоелементне - на їхкомбінації.
Закількістюсимволівкодиможнарозподілитина:одиничні,двійковітанедвійкові.Кількістьсимволівназиваєтьсяосновоюкоду.Взалежностівідметодупобудовирозрізняютькоди,щовикористовуютьусімож-ливікомбінації-кодинавсісполученнятакоди, щовикористовуютьлишечастинуможливихкомбінацій.Крімтого,вонирозподіляютьсянакоди, щоневиявляютьспотворення,коди,щовиявляютьспотвореннятакоди, щовиявляютьтавиправляютьспотворення.Втеперішнійчаснайчастішевикористовуютьдвійковікоди.
Системичислення
Методикапобудовикодівтіснопов’язаназвідповіднимисистемамичислення.Побудовасистемичисленнязалежитьвідїїоснови, тобтокількості цифр, з якихможнаодержати будь-яке число.
Так,десятковасистемабазуєтьсянацифрахвід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 = { xi }, i = 1, 2,..., N - ансамбль взаємнонезалежнихповідомлень з апріорнимиймовірностями p (xi), ay = { yk }, k = 1, 2,..., L - ансамбль символів коду L <N, то число кодовихслів по n символівв кожному слові M = Ln.
При Ln ≥ N, де n - найменшеціле число, для якоговиконуєтьсяцянерівність.
Приклад 1Закодувати за методом Шеннона - Феноповідомлення з N = 24 символів:
математика_ - _царица_наук
Рішення. Випишемо в таблицючастоти ni та ймовірності pi = появикожноїбуквиповідомлення
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) = pilnpi=+ 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 = 2n,
де 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= 1. Значение k 2форми-
руется из всех k 2 для которых т 1 = 1, и т.д. Напередатчик канала связи подается
самокорректирующийся код Хэмминга [7, 4], который имеет вид
(т 1, т 2, к1, т 3, к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).
