Основні операції над елементами поля

Основа (алфавіт) q коду може мати різні значення (q ≥ 2). Методика побудови багатьох кодів ґрунтується на використан­ні властивостей послідовностей двійкових чисел. Розглянемо деякі операції над елементами двійкових кодів (q = 2).

Правила додавання за модулем 2 визначаються такими опе­раціями:

0 0 = 0; 1 1=0; 0 1 = 1; 1 0=1.

;

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

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

При діленні за модулем 2 дільник підписують під діленим так, щоб збігалися старші розряди. Якщо кількість розрядів діленого перевищує або дорівнює кількості розрядів дільника, то в частку переносять 1, після чого виконують додавання за модулем 2 й до здобутого числа дописують праворуч наступну цифру діленого. Якщо ж число остачі разом з дописаною циф­рою, дорівнює кількості розрядів дільника, то до частки допи­сують ще одну 1, а якщо ні - то 0 доти, доки кількість розрядів остачі не дорівнюватиме кількості розрядів дільника. Після цього виконують додавання за модулем 2. Операцію повторю­ють стільки разів, поки всі розряди діленого не перенесуться до остачі. Наприклад:

Дуже зручно операції додавання, віднімання, множення та ділення.за модулем 2 виконувати з двійковими числами, запи­саними у вигляді поліномів.

V ₁(х ) = х ⁵ + х ⁴ + х; V ₂(х) = х ⁵ + 1.

V ₁(х) V ₂(х)= х ⁵ + х ⁴ + х + х ⁵ + 1 = х ⁴ + х + 1 → 010011.

V ₁(х) V ₂(х) = (х ⁵ + х ⁴+ x)(x ⁵ + 1) = х ¹⁰+ х ⁹+ х ⁶ + х ⁵ + х ⁴ +х → 11001110010.

V ₁(х) :V ₂(х) = (х ⁵ + х ⁴+ x): (x ⁵ + 1) = .

 

Способи подання кодів

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

Перший спосіб полягає в поданні коду у вигляді таблиці всіх його комбінацій. Наприклад, п'ятиелементний двійковий бло­ковий код зі сталою вагою, в кожній комбінації якого містяться три одиниці, задається так табл.5.1:

Таблиця 5.1- Спосіб подання коду з вагою 3

 

Номер кодової комбінації	Комбінація двійкового блокового коду з вагою 3

 

 

Продовження табл.5.1

 

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

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

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

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

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

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

а)

б

Рисунок 5.2- Приклад побудови кодових дерев; а) рівномірного двоелементного двійкового; б) нерівномірного двійкового.

 

Третій спосіб подання кодів полягає в зображенні комбіна­цій коду точками дискретного n -вимірного векторного просто­ру. Так, кожну комбінацію рівномірного блокового коду (з ос­новою q і довжиною n) V= (V_п , V_{п- 1},..., V ₂ , V ₁ ) можна розглядати як вектор або точку деякого n -вимірного векторного простору з координатами V_п , V_{п- 1},..., V ₂ , V ₁. Якщо значення q скінчен­не, а будь-яка координата вектора є цілим додатним числом від 0 до q - 1, то зазначений код можна розглядати як дискретний n -вимірний простір, що складається з N= q^п точок, які відпові­дають кінцям усіх можливих векторів.

Цей n -вимірний простір дістав назву кодового. Кількість просторових вимірювань кодового простору для коду з будь-якою основою дорівнює довжині n коду, а кількість градацій по кожній з осей (напрямків вимірювання) визначається осно­вою коду і становить q -1.

Якщо для дискретного n -вимірного простору, що тут роз­глядається, ввести поняття кодової відстані d між точками V_і та V_j,то матимемо

. (5.2)

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

Для визначення кодової відстані між комбінаціями коду з основою q треба виконати їх порозрядне віднімання за моду­лем q.

З'єднавши кожну точку простору, що розглядається, прями­ми лініями з усіма точками, віддаленими на відстань d (V_i , V_j )= 1, дістанемо геометричну фігуру сіткової структури. Цю фігуру називають геометричною моделлю n -елементного q -коду.

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

а)

б)

Рисунок 5.3 – Геометричні моделі кодів; а) двоелементний код; б) триелементний код.

На рис. 5.2 зображено геометричні моделі деяких кодів. На рис. 5.2, а – двовимірний просторовий код.На рис. 5.2, б – триелементний код.

Четвертий спосіб подання кодів у вигляді матриці з 2 ⁿ ряд­ками та п стовпцями можливий тільки для рівномірних n -еле­ментних двійкових блокових кодів. Якщо матрицею подається сукупність ненульових комбінацій коду, то кількість рядків дорівнюватиме 2 ⁿ - 1.