ТОП 10:

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



Основа (алфавіт) 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 виконувати з двійковими числами, запи­саними у вигляді поліномів.

V1(х) = х5 + х4 + х; V2(х) = х5 + 1.

V1(х) V2(х)= х5 + х4 + х + х5 +1 = х4 + х + 1 → 010011.

V1(х) V2(х) = (х5 + х4+ x)(x5 + 1) = х10+ х9+ х6 + х5 + х4+х → 11001110010.

V1(х):V2(х) = (х5 + х4+ x) : (x5 + 1) = .

 

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

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

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

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

 

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

 

 

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

 

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

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

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

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

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

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

а)

б

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

 

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

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

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

. (5.2)

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

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

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

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

а)

б)

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

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

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

 







Последнее изменение этой страницы: 2017-02-07; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 35.168.112.145 (0.004 с.)