Завдання на виконання лабораторної роботи. Побудова і дослідження роботи схем кодеків циклічних кодів

ЗАВДАННЯ

На виконання лабораторної роботи

Побудова і дослідження роботи схем кодеків циклічних кодів.

Мета заняття: поглиблене засвоєння студентами процесів кодування і декодування при застосуванні циклічних кодів.

1. Основні теоретичні положення

Циклічні коди відрізняються високою ефективністю виявлення помилок і порівняно простою реалізацією кодуючих і декодуючих пристроїв у вигляді регістрів з зсувом і зворотними зв’язками.

Циклічний код це код, у якого з приналежної йому комбінації

аn-1,..., а1 ,а0.

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

а0, аn-1,..., а1.

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

При кодуванні багаточлен G(x), що відображає двійковий код повідомлення, яке підлягає передачі, помножують на хr. Це збільшує довжину кодової комбінації на r розрядів, які потрібні для запису у них перевірочних розрядів.

Добуток G(x) xr ділять на утворююч ий поліном Р(х), а залишок R(x) від цього ділення складають з G(x) xr, тобто записують залишок у r молодших розрядів(де після зсуву – перемноження на хr записані нулі). Отриманий поліном F(x)= G(x)xr R(x) є комбінацією, що ділиться без залишку на Р(х), тобто він є дозволеною комбінацією даного циклічного коду.

Дійсно, якщо f(x) є частка від ділення G(x) xr на Р(х), то

G(x) xr = f(x) P(x) R(x). (43)

Додавши за модулем 2 до правої та лівої частини R(x) отримуємо

G(x) xr R(x)= f(x) P(x), (44)

Тобто, комбінація F(x) =G(x) xr R(x) дійсно ділиться на Р(х) без залишку.

До циклічних кодів відносяться коди Боуза-Чоудхурі-Хоквінгема (БЧХ).

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

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

Регістр зсуву з зворотними зв’язками будується у відповідності до обраного утворюючого багаточлена за такими формальними правилами (теоретичною базою побудови таких пристроїв є теорія кінцевих автоматів з пам’яттю):

1. Число каскадів (тригерів) регістра обирають рівним степені () утворюючого багаточлена.

2. Кількість суматорів за модулем 2 береться на одиницю менше числа ненульових членів утворюючого багаточлена.

3. Входи всіх тригерів регістра позначають хі (і=0, 1, 2). Вихід останнього тригера позначається , а вхід першого – х0.

4. Суматори за модулем 2 встановлюються на вході тих тригерів, для яких у формулі утворюючого багаточлена коефіціент при відповідній степені хі має ненульове значення. Наприклад, для Р(х) =х3+х+1 (див. рис. 1) суматори встановлюються на входах 1 та 2 (тригерів, що відповідають х0 та х).

5. Вихід останнього тригера з’єднується з одним із входів суматорів.

6. Виходи попередніх тригерів з’єднуються з входами наступних через суматори (в залежності від того, встановлені вони між тригерами чи ні) або безпосередньо.

Кл1

Кл2; Вих

Х0 Х1 Х2

Рис. 1

2. Завдання на лабораторну роботу.

2.1 Побудова кодеру і дослідження процесу кодування.

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

Представити свої ініціали у двійковому коді, наприклад, у міжнародному телеграфному коді МТК-2, додавши у старшому розряді 1 при розташуванні літери на регістрі кирилиці або 0 при розташуванні літери на регістрі чисел та символів, (або у коді Бодо; у коді АSKII, тощо), після чого:

а) визначити відстані Хемінга між кодовими комбінаціями першої та другої, другої та третьої, першої та третьої літер;

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

При цьому необхідно:

-  отримати залишки шляхом ділення інформаційних складових на утворюючий поліном;

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

в) визначити кодову відстань між представленими у циклічному коді літерами ініціалів;

г) у відповідності з кодоутворюючим поліномом розробити функціональну схему кодуючого пристрою;

д) відобразити процес отримання залишку (у вигляді двійкової послідовності) шляхом покрокового заповнення таблиці стану тригерів регістру кодуючого пристрою (для кожної літери);

2.2 Побудова декодеру і дослідження процесу декодування.

Дослідити процес декодування повідомлення закодованого завадостійким циклічним кодом:

а) перевірити правильність сформованих кодових слів шляхом ділення їх на утворюючий поліном (залишки повинні дорівнювати нулю);

б) перевірити здатність коду виявити помилки певної кратності, для чого ввести помилки у вигляді багаточлена помилки Е(х), взятого за завданням викладача із переліку у Додатку 1, додавши його до багаточленів кодових слів першої, другої та третьої літер;

в) визначити надлишковість та відносну швидкість коду;

г) визначити, чи може код забезпечити виявлення помилок кратності 2 та 3;

д) відобразити процес отримання синдрому (залишку) при декодуванні у відсутності помилок шляхом покрокового заповнення таблиці стану тригерів регістру декодуючого пристрою (для першої та другої літери);

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

Порівняти та проаналізувати результати, отримані вище.

3. Приклад виконання.

Іваненко Петро Семенович

Ініціали ІПС можна закодувати з використанням того чи іншого двійкового коду відповідних літер. Наприклад, за номером літери у алфавіті (без урахування ґ та пробілу). Літера І - 10, П - 19, С - 21. У двійковому п’ятизначному коді коди літер відповідно будуть такими: І - 01010, П - 10011, С - 10101.

а) Відстані Хемінга:

Математична модель кодування циклічним кодом.

б) Кодування циклічним кодом з поліномом Р(х)= х3+х+1.

Кодуємо літеру

отримуємо залишок діленням на P(x).

x6+x4 !x3+x+1

x6+x4+x3! x3+1

0 0 x3

x3+x+1

x+1=RI(x)

Кодове слово завадостійкого циклічного коду буде мати вигляд .

. Враховуючи, що його розрядність п повинна дорівнювати 8 (п’ять інформаційних розрядів і три перевірочні), то у двійковому коді це буде =.

Таким же чином отримують .

Математична модель декодування циклічного коду.

Перевірка вірності формування декодуванням. Ділимо на

x6+x4+x+1 !x3+x+1

x6+x4+x3 ! x3+1

0 0 x3+x+1

x3+x+1

0 0 0

Залишок дорівнює нулю. Перевірочні розряди отримані вірно.

Аналогічно перевіряють

в) Визначення аналогічно пункту а).

г) Перевіряємо можливість виявлення помилок. Нехай багаточлен помилки Е(х)=х5+1(кратність помилки 2)

Спотворене кодове слово буде

ділимо на

x6 + x5 + x4 + x !x3+x+1

x6 + x4 + x3 ! x3+x2

0 + x5 + x3+ x

x5 + x3 +x2

0 0 x2 +x

- залишок не дорівнює нулю. Помилка виявлена.

д)Надлишковість коду 3/8; відносна швидкість 5/8.

є) Для визначення можливостей коду щодо виявлення помилок кратності 2 і 3 необхідно встановити відповідність наявної кількості перевірочних розрядів вимогам з виявлення помилок заданої кратності скориставшись верхнею межею Хемінга.

Дослідження функціональної моделі кодуючого пристрою.

е)У відповідності до наведених вище у теоретичній частині правил поліному Р(х)= х3+х+1 відповідає кодуючий пристрій, представлений на рис. 2.

Кл1

Кл2; Вих

Х0 Х1 Х2

Рис. 2

ж) Формування перевірочних розрядів за допомогою кодуючого пристрою.

На вхід кодера (див. рис. 2) старшими розрядами вперед подається послідовность нулів та одиниць (див. Таблицю 3), яка відповідає багаточлену . Процес кодування відображено у таблиці 3. Розряди кодової комбінації покроково просуваються від тригера до тригера. Зворотній зв’язок не впливає на їх значення, тому що ключ 1 (КЛ1) у розімкненому стані. Після r-того кроку (у прикладі, що розглядається, - після третього) замикається ключ 1 і розмикається ключ 2 (КЛ2). Зворотній зв’язок починає впливати на значення тих розрядів, які записуються у тригери, перед якими встановлені суматори за модулем 2.

Таким чином на восьмому кроці отримано залишок, який дорівнює 011, що відповідає поліному RI(x)= x+1 і дозволяє сформувати кодове слово

.

У двійковому вигляді це =.

(Інфраструктура кодера, яка забезпечує процедуру використання отриманого залишку для формування дозволеного кодового слова на рисунку не показана. Детальніше див. [6])

Таблиця 3

№кроку	Вхідна послідовність	Стан тригерів
X0	X1	X2
1	0000101	0
2	000010	1	0
3	00001	0	1	0
4	0000	1	0	1
5	000	1	0	0
6	00	0	1	0
7	0	0	0	1
8		1	1	0

Дослідження функціональної моделі декодуючого пристрою.

з) Декодування при відсутності помилок (перевірка правильності формування кодового слова).

На вхід декодера (рис. 2) старшими розрядами вперед подається послідовність =. Процес декодування відображено у таблиці 4.

Таблиця 4

№кроку	Вхідна послідовність	Стан тригерів
X0	X1	X2
1	1100101	0
2	110010	1	0
3	11001	0	1	0
4	1100	1	0	1
5	110	1	0	0
6	11	0	1	0
7	1	1	0	1
8		0	0	0

Залишок дорівнює нулю. Кодове слово (у двійковому вигляді ) сформоване вірно і є дозволеним. Це відповідає випадку його прийому у відсутності помилок.

Таким же чином дослідити декодування решти кодових слів.

і) Декодування при наявності помилки (перевірка виявлення помилки), структура якої відповідає поліному Е(х).

Необхідно декодувати послідовність, що відповідає багаточлену спотвореного кодового слова

.

У двійковому вигляді = . Цю послідовність подаємо старшими розрядами вперед на декодуючий пристрій. Процес декодування відображено у таблиці 5.

Залишок (синдром) (і він співпав з отриманим при математичному моделюванні); помилка виявлена.

Таким же чином дослідити декодування решти спотворених кодових слів.

Таблиця 5

№кроку	Вхідна послідовність	Стан тригерів
X0	X1	X2
1	0100111	0
2	010011	1	0
3	01001	1	1	0
4	0100	1	1	1
5	010	1	0	1
6	01	1	0	0
7	0	1	1	0
8		0	1	1

Порівняти і проаналізувати всі отримані результати. Оформити звіт про лабораторну роботу.

ЛІТЕРАТУРА

1. Радиотехнические системы передачи информации. Учебное пособие для вузов / , , и др. / Под ред. - М.: Радио и связь, 19с.

2. Игнатов информации и передачи сигналов. - М.: Радио и связь, 19с.

3. Кузьмин теории информации и кодирования. - К.: Вища школа, 19с.

4. Цымбал информации и кодирования. - К.: Вища школа, 19с.

5. , Полтырев теории информации. - М.: Наука, 19с.

6. , Лосев информации в АСУ. - М.: Сов. радио, 19с.

7. Теория передачи сигналов. / , , . - М.: Радио и связь, 1986.

8. , Полторак ія інформації та кодування: Підручник. – К.: Вища школа, 2001. – 255 с.

9. Алгебраическая теория кодирования. - М.: Мир, 1878.

10. Финк передачи дискретных сообщений. – М.: Сов. радио, 1970.

11. Цымбал по теории информации и кодированию. – Киев: Вища школа, 1976.

12. Теория и практика кодов, контролирующих ошибки: Пер. С англ. – М: Мир, 1986. – 576 с.

13. Теория кодирования: Пер. с яп. / Т. Касами, Н. Токура, Е. Ивадари, Я. Инагаки. – М.: Мир, 1978. – 576 с.

Розробив викладач

Додаток 1.

№вар	Р(х)	Е(х)
1	х3+х2+1	х6+1
2	х4+х+1	х8+х4
3	х5+х+1	х+1
4	х4+х3+1	х5+х4+1
5	х3+х2+х	х4+х+1
6	х5+х2+1	х3+1
7	х4+х2+1	х5+х2+х+1
8	х4+х3+х2	х4+1
9	х5+х4+1	х7+х+1
10	х5+х3+1	х4+ х3
11	х5+х4+х3	х8+х3+х2
12	х5+х4+х2+х+1	х9+х4+1
13	х4+х3+х	х6+1
14	х3+х+1	х8+х7
15	х5+х2+х	х8+х7+1
16	х4+х2+х	х4+х3
17	х5+х4+х	х2+х+1
18	х5+х3+х2+х+1	х5+х3 +1
19	х5+х4+х2	х5+х+1
20	х5+х2+х	Х5+х2
21	х4+х3+х2+х+1	х4+х2+х
22	х5+х3+х	х8+х
23	х3+х2+х+1	х5+х3+1
24	х5+х3+х2	х9+1
25	х5+х4+х3+х2+1	х5+х2+х
26	х4+х3+х2+1	х7+х4
27	х5+х4+х3+х+1	х8+х3
28	х5+х2+х+1	х5+х2+х+1
29	х4+х3+х2+х	х5+х4
30	х5+х3+х2+х	х7+х2
31	х4+х2+х+1	х9+ х3+1
32	х6+х4+х3	х7+ х3+1
33	х4+х3+х2+1	х8+х2
34	х6+х3+1	х9+х4+1
35	х5+х4+х+1	х7+1
36	х5+х3+х2+1	х9+ х8+х

Додаток 2.

Міжнародний телеграфний код №2