Лабораторна робота №2 Вивчення властивостей і принципів побудови циклічних кодів.

1 Ціль роботи

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

2 Методичні вказівки

При підготовці до виконання лабораторної роботи необхідно вивчити теми 9,10 по конспекту лекцій та рекомендовану літературу [1, с. 120 - 126; 3, с. 93 - 101; 6, с. 230 - 239]. Особливу увага звернути на наступні основні положення.

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

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

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

Будь-яка комбінація циклічного коду містить n розрядів (символів).

n=k+r -число символів у кодовій комбінації (або число розрядів). n визначає розрядність двійкового багаточлена, що описує кодову комбінацію.

F(x) – двійковий n-розрядний багаточлен, що представимо у вигляді

,

де коефіцієнти а_i приймають значення "1" або "0" і відповідають двійковим символам кодової комбінації.

Над двійковим багаточленом роблять операції:

• додавання;

• віднімання;

• множення;

• ділення.

Додавання та віднімання двійкових багаточленів – це додавання коефіцієнтів при відповідних ступенях х по модулю два.

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

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

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

.

Стандартний запис:

.

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

В основі виконання операцій кодування та декодування циклічних кодів лежить використання утворюючих багаточленів.

Утворюючий багаточлен G(х) – це багаточлен (поліном), що не приводиться, максимального ступеня r, отже, розрядність G(х) є r+1.

Тільки вибір багаточлена, що не приводиться, у якості утворюючого забезпечує однозначність при виправленні помилок. Відомо: М₀ – число кодуємих повідомлень алфавіту (число рівнів квантування). Тоді необхідна кількість інформаційних символів

- округлення до найближчого більшого цілого числа.

g – кратність помилок, що виправляють. G(х) визначається по таблицях після обчислення r по відомим значенням g, М₀, k.

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

V(x) – багаточлен первинного коду на первинному кінці лінії зв'язку. Розрядність V(x) дорівнює k.

Існує два способи формування комбінацій F(x) циклічного коду.

1. F(x)=G(x)V(x) – розрядність k+r.

2. V(x)x^r/G(x)=Q(x)+R(x) – розрядність k+r.

де: x^r - багаточлен ступеня r, R(x) – залишок від ділення (розрядність r).

F(x)=V(x)x^r+R(x)– розрядність k+r.

F(x) – це комбінація циклічного коду, що передається по каналу зв'язку.

Недолік першого способу: інформаційні та контрольні символи посідають довільні місця в кодовій комбінації, що ускладнює декодування (на практиці не використовується).

На прийомному кінці: F*(x).

Алгоритм перевірки

R*(x)=0 – це означає, що в кодовій комбінації помилки немає або кодова комбінація переходить в іншу дозволену комбінацію і помилка не виявляється.

R*(x)≠0 свідчить про наявність помилки.

Якщо у якості утворюючого багаточлена обирається неприводимий багаточлен, то число різних залишків дорівнює 2^r-1 за умови, що вага вектора помилки w≤g.

Вектор помилки:

, (k+r) – розрядність вектора помилки.

Вага вектора помилки - це число одиниць у векторі помилки.

Залишок R*(x), одержуваний при діленні прийнятої комбінації F*(x) на утворюючий поліном G(х) та вектора помилки Е(х) на G(х), в обох випадках однаковий.

R*(x) у цьому випадку відіграє роль синдрому або контрольного числа.

Розглянемо загальний алгоритм виявлення та виправлення однократних помилок(g=1). Число можливих варіантів помилок – k+r.

1. Ділимо прийняту кодову комбінацію на утворюючий поліном G(x).

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

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

4. У результаті всіх перерахованих вище дій одержують виправлену кодову комбінацію.