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

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

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

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

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

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

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

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

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

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

Десяткова

Двійкова

Вісімкова

Шістнадцяткова

0

0000

00

00

1

0001

01

01

2

0010

02

02

3

0011

03

03

4

0100

04

04

5

0101

05

05

6

0110

06

06

7

0111

07

07

8

1000

10

08

9

1001

11

09

10

1010

12

0A

11

1011

13

0B

12

1100

14

0C

13

1101

15

0D

14

1110

16

0E

15

1111

17

0F

16

10000

20

10

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

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

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

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

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

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

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

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

При LnN , де 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) = 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

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

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

А

000

И

011

Р

1100

_

001

М

100

Н

1101

Ц

0100

Т

1010

У

1110

К

0101

Е

1011

-

1111

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

п

3

4

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

1100111

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

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

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

Символ

Двій- ковий

Код Грея

ASCII

0

0000

0000

30

1

0001

0001

31

2

0010

0011

32

3

0011

0010

33

4

0100

0110

34

5

0101

0111

35

6

0110

0101

36

7

0111

0100

37

8

1000

1100

38

9

1001

1101

39

10

1010

1111

31 30

11

1011

1110

31 31

12

1100

1010

31 32

13

1101

1011

31 33

14

1110

1001

31 34

15

1111

1000

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, тому для семиелементної комбінації розташування символів кодове слово має вигляд:

k4 k3 k2 m3 k1 m2 m1 ;(9.3)

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

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

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

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

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

m3

m2

m1

Символи

0

0

1

m1

т1 = к1 ⊕ к2 ⊕ к4

т 1 = к1 ⊕ к3 ⊕ к4

т 2 = к2 ⊕ к3 ⊕ к4

0

1

0

m2

0

1

1

k1

1

0

0

m3

1

0

1

k2

1

1

0

k3

1

1

1

k4

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

руется из всех k2 для которых т 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).

← Предыдущая
Страница 1
Следующая →

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

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Способы представления статистических данных

Значение графического метода в анализе и обобщении данных велико. Графическое изображение, прежде всего, позволяет осуществить контроль достоверности статистических показателей, так как, представленные на графике

Программы спортивной подготовки. Олимпизм

Программа спортивной подготовки - программа поэтапной подготовки физических лиц по виду спорта (спортивным дисциплинам), определяющая основные направления и условия спортивной подготовки на каждом ее этапе.

Инфекционные болезни. Тест с ответами

Тесты с ответами по инфекционным болезням. Указать один или несколько правильных ответов. Тестирование.

Истечение, Дросселирование, Смешение паров и газов

Физика. Вопросы к дифференцированному зачёту

Сохранить?

Пропустить...

Введите код

Ok