Правило додавання за модулем 2

0 0=0;

0 1=1;

1 0=1;

1 1=0.

Наприклад, при додаванні за модулем 2 двійкових послідовностей чисел 0111000 і 10010 матимемо

,

тобто, результатом додавання цифр певного розряду є «0», якщо сума одиниць у ньому парна, і «1», якщо сума одиниць у ньому непарна.

На відміну від звичайного арифметичного додавання операція додавання двійкових чисел за модулем 2 полягає в тому, що в даному разі розглядають конкретну пару двійкових знаків незалежно від інших чисел двійкової послідовності. Тому результат попередніх операцій при додаванні чергової пари двійкових знаків не враховують, тоді як при звичайних арифметичних операціях цей результат треба враховувати обов'язково, коли при додаванні двох двійкових чисел (наприклад, одиниць) записується 0, а 1 переноситься в старший розряд.

Правило віднімання за модулем 2 нічим не відрізняється від операції додавання.

Правило множення за модулем 2

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

11

* 11

Å 11_

Правило ділення за модулем 2

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

10001 | 101

Å 101 | 101

Å 101

Задача 4.1 (для самостійного розв’язання)

Виконати додавання за модулем 2 двійкових чисел 1001 та 111. Виконати множення двійкових чисел 1111 і 1101. Розділити двійкове число 1001011 на 1101; 10101 на 1011.

Кодова відстань

Кодова відстань Хеммінга d між двома кодовими комбінаціями визначається порозрядним додаванням їх за модулем 2 та подальшим підрахунком кількості ненульових елементів, тобто визначенням ваги w такої суми.

 

Задача 4.2

Визначити кодову відстань між комбінаціями А і В двійкового коду та записати всі комбінації, які знаходяться від комбінації А на кодовій відстані d= 3, якщо А =01001, В =11101.

Розв'язання. Щоб визначити кодову відстань між комбінаціями А та В, знаходимо поелементну суму за модулем 2 цих комбінацій:

,

одержуємо комбінацію C =10100, вага якої w= 2. Тобто, в комбінаціях А і В у трьох однойменних розрядах (на 1-му справа, 2-му і 4-му) знаходяться однакові символи, а на двох (на 3-му справа і 5-му) – різні, сукупність яких і визначає степінь різниці між комбінаціями А та В. Вага комбінації С є кодовою відстанню Хеммінга між комбінаціями А та В.

Будь-яка комбінація ваги w = 3, якщо її порозрядно додати за модулем 2 до комбінації A (такої ж довжини), дає нову комбінацію, яка буде знаходитися від комбінації A на кодовій відстані d= 3. Кількість таких комбінацій буде дорівнювати кількості сполучень з n =5 по d =3:

Ці комбінації одержуємо, додаючи порозрядно до комбінації А почергово всі десять комбінацій з вагою 3:

 

 

Таким чином одержуємо такі 10 комбінацій, які знаходяться від комбінації А на кодовій відстані d= 3: 01110, 00010, 00100, 00111, 11010, 11100, 11111, 10000, 10011, 10101.

Задача 4.3 (для самостійного розв’язання)

Згідно з варіантами, поданими в таблиці 4.1, визначити кодову відстань між двійковими комбінаціями А та В двійкового коду та занести результати у табл. 4.1. Записати всі комбінації, які знаходяться від комбінації А = 10101 на кодовій відстані d = 2, 3, 4.

Таблиця 4.1

№ варіанта	Двійкові кодові комбінації	Кодова відстань між А і В, d
А	В

 

Задача 4.4 (для самостійного розв’язання)

Згідно з варіантами, поданими в таблиці 4.2, визначити мінімальну та максимальну кодові відстані Хеммінга d між комбінаціями А, В, С, D двійкового n -елементного простого коду. Результати занести у табл. 4.2.

Таблиця 4.2

№ варі-анта	Двійкові кодові комбінації	dmin	dmax
A	B	C	D

 

5. Способи подання кодів. Кодові дерева.

Код кожного виду має свій найраціональніший спосіб подання, що випливає з його властивостей. Проте відомо також кілька загальних способів подання кодів, які є досить універсальними і можуть застосовуватися для опису широких класів кодів. До цих способів належать подання кодів у вигляді: 1) таблиць кодових комбінацій; 2) кодового дерева; 3) геометричної моделі; 4) матриці. Розглянемо більш детальніше перші два способи.

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

Таблиця 5.1

№ КК	Букви	Двійкові КК простого коду	Двійкові КК простого коду	Двійкові КК простого коду
	А
	Б
	В
	Г
	Д
	Е
	Ж
	З

 

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

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

Вузли кодового дерева розташовуються на різних рівнях. Кожний рівень дерева рівномірного коду може мати qⁱ вузлів, де q — основа коду, і — номер рівня (i = 1,2,...,п, тут п — довжина коду). Для рівномірного двійкового простого коду кількість вузлів на останньому рівні п дорівнює кількості N комбінацій коду, тобто 2ⁿ=N.

Вузли, що не з'єднуються з наступними рівнями, називаються кінцевими, вони відповідають комбінаціям коду.

Основою коду обмежується максимальна кількість ребер, яка може виходити з кожного вузла дерева, а максимальною довжиною кодової комбінації — максимальна кількість рівнів кодового дерева. Кожному вузлу приписується значення розрядів комбінації, що відповідає напрямкам руху вздовж ребер від кореня дерева до вузла. Ребра, що йдуть від кореня до вузлів першого рівня, визначають значення першого зліва розряду кодової комбінації, а ті, що з'єднують вузли першого та другого рівнів, — значення другого зліва розряду і т. д. На рис. 5.1 показано приклади кодових дерев: рівномірних двоелементного двійкового (рис. 5.1, а), двоелементного трійкового (рис. 5.1,6), триелементного двійкового (рис. 5.1, в) та нерівномірного двійкового (рис. 5. 1, г). Цей спосіб застосовується для зображення як блокових, так і неперервних кодів.

 

 

За допомогою кодових дерев легко зобразити префіксні коди, що мають властивість префікса й можуть бути утворені послідовним викреслюванням останнього розряду кодової комбінації, причому жодна з комбінацій даного префіксного коду не може бути префіксом його комбінації. Наприклад, префіксами кодової комбінації 10111001 будуть 1, 10, 101, 1011, 10111, 101110, 1011100, 10111001, тобто для однозначного її декодування жодна з комбінацій цього коду не повинна мати перелічені вище комбінації. Отже, однозначне декодування забезпечують коди, в яких жодна з більш коротких кодових комбінацій не збігається з початковою частиною кожної більш довгої кодової комбінації. Такі коди називають префіксними. Кожний кінцевий вузол кодового дерева префіксного коду відповідає комбінації префіксного коду

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

Задача 5.1

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

Розв'язання. Максимальна довжина п=4 нерівномірного двійкового коду визначає кількість рівнів кодового дерева; тому воно матиме вигляд, показаний на рис. 5.2. Для побудови дерева від кореня проводяться відрізки прямої (ребра), які мають нахил вліво, якщо кодовий символ є «0», і які мають нахил вправо, якщо кодовий символ є «1».

Рис. 5.2

З рисунка випливає, що кількість комбінацій (1, 01, 001, 0000, 0001) цього коду дорівнює п'яти.

Задача 5.2 (для самостійного розв’язання)

Задати за допомогою кодового дерева комбінації двійкових простих кодів, поданих у таблиці 5.1, та навести основні характеристики цих кодів.

 

Контрольні запитання:

1. Назвіть основні характеристики кодів.

2. Чим відрізняються рівномірні коди від нерівномірних?

3. Які основні відмінності операцій множення та ділення двійкових чисел від арифметичних?

4. Як знайти мінімальну кодову відстань між кодовими комбінаціями коду?

5. У чому полягає спосіб представлення коду у вигляді кодового дерева?