Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Проблемно-орієнтовані методи та засоби інформаційних технологій
Група:
К
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ЦИКЛІЧНІ КОДИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи з курсу
“Проблемно-орієнтовані методи та засоби інформаційних технологій”
для студентів базового напрямку 6.0305 “Філологія”
Затверджено
на засіданні кафедри
“Системи автоматизації проектування”
Протокол № 9 від 07.02.2002 р.
Львів – 2002
Циклічні коди: Методичні вказівки до лабораторної роботи з курсу “Проблемно-орієнтовані методи та засоби інформаційних технологій” для студентів базового напрямку 6.0305 “Філологія”.
/Укл.: В.В. Мазур. – Львів: Видавництво Національного університету“Львівська політехніка”, 2002. - 10 с.
Укладач Мазур В.В., канд. техн. наук, доц.
Відповідальний за випуск Ткаченко С.П., канд. техн. наук, доц.
Рецензенти Кравець П.О., канд. техн. наук., доц.
Стех Ю.В., канд. техн.наук.,доц.
МЕТА РОБОТИ
Мета роботи - вивчення методiв завадостійкого кодування (циклічні коди) та особливостей їх програмної і апаратурної реалiзацiї.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Побудова і застосування циклічних кодів.
Коди називаються циклічними, якщо частина чи всі дозволені кодові комбінації для них можуть бути отримані шляхом циклічного зсуву однієї або кількох комбінацій. Циклічний зсув здійснюється справа наліво, причому крайній лівий символ переноситься в кінець комбінації. Циклічні коди відносяться до лінійних блочних кодів.
Побудова циклічних кодів базується на використанні неприводимих у полі двійкового числа поліномів. Неприводимі поліноми діляться без остачі тільки на себе і на одиницю.
Корекція помилок в циклічних кодах базується на тому, що дозволені комбінації коду мають ділитися без остачі на деякий утворюючий поліном, який вибирається з набору неприводимих.
Для отримання циклічного коду для заданої комбінації інформаційних бітів (наприклад, I(x)=x3+x2+1=1101) вона домножується на одночлен тієї ж степені (n=3), що і утворюючий поліном (K(x)=x3+x+1=1011). Це еквівалентно приписуванню n нулів справа у двійковому представлення коду (I(x)*xn=(x3+x2+1)*x3= x6+x5+x3=1101000).
Значення коректуючих розрядів знаходимо в результаті ділення I(x)*x3 на K(x)
I(x)*x3 / K(x)=x6+x5+x3/(x3+x+1)= x3+x2+x+1+1/(x3+x+1)
або у загальному випадку
I(x)*xn/K(x)=Q(x)+R(x)/K(x)
де: Q(x) - частка, а R(x) - остача.
F(x)=Q(x)*K(x)=I(x)*xn+R(x)
Для нашого прикладу
F(x)=(x3+x2+x+1)*(x3+x+1)=(x3+x2+1)*x3+1
або
F(x)=1111*1011=1101001=1101000+001
Це і буде кодова комбінація, яка визначалась. Причому, 1101 – інформаційна частина , а 001 – контрольна .
Як початкові беруться комбінації одиничної матриці. В результаті знаходження остачі можемо знайти утворюючу матрицю. Сумуванням по модулю 2 всіх можливих поєднань рядків утворюючої матриці знаходимо решту комбінацій циклічного коду.
Для знаходження і виправлення помилок в циклічних кодах отримані після передачі по каналу зв’язку комбінації діляться на утворюючий поліном для знаходження остачі. При діленні для бітів використовується не віднімання, а операція XOR. Циклічний зсув отриманої комбінації і ділення на утворюючий поліном здійснюють до тих пір поки кількість одиниць в остачі буде менша або рівна значенню коректуючої властивості коду (в нашому випадку виявляється і коректується одна помилка у коді). При цьому, якщо остача рівна нулю, то кодова комбінація правильна, а якщо не рівна нулю, то сума (по модулю 2) остачі з отриманою кодовою комбінацією дасть правильну кодову комбінацію.
Утворюючий поліном відповідної степені вибирається з таблиць, приведених в літературі, на основі відомої довжини інформаційної частини коду. Наприклад для інформаційної частини довжиною чотири біти утворюючий поліном має степінь 3 і може приймати значення 1011 або 1101. Для позначення кодів використовується пара (j.k), де: j – загальна довжина коду, а k – довжина контрольної частини (наприклад (7.3)).
Приклад побудови циклічного коду і виявлення та виправлення поодинокої помилки. Нехай інформаційна частина коду (7.3) рівна 1101. Дописуємо справа три нулі на місце контрольних розрядів (степінь утворюючого полінома n=3) і ділимо отриману бітову послідовнисть на утворюючий поліном для знаходження остачі (рис.1 а). Потім замінюємо контрольні розряди розрядами остачі і отримуємо потрібну кодову комбінацію, яка тепер ділиться на утворюючий поліном без остачі (рис 1 б). У відповідності із властивістю циклічних кодів всі коди отримані в результаті циклічного зсуву початкового теж діляться без остачі на утворюючий поліном (рис.1 в-г). При внесенні помилки в один із розрядів отриманого коду, наприклад в п’ятий (розряди нумеруються справа наліва від 0 до 6), в результаті ділення на утворюючий поліном остача буде нерівна нулю, що вказує на наявність помилки (рис.1 д). Помилковий код циклічно зсувається і ділиться на утворюючий поліном до тих пір поки не отримаємо остачу з одиницею в останньому розряді (рис.1 е-ж). Після цього здійснюється корекція коду і циклічний зсув у зворотньому напрямку (рис.1 з).
а б в г
1101000/1011 1101001/1011 1010011/1011 … 0110100/1011
1011 1011 1011 1011
------ ------ ------ ------
1100 1100 1011 1011
1011 1011 1011 1011
------ ------ ------ ------
1110 1110 0 0
1011 1011
------ ------
1010 1011
1011 1011
------ ------
1 0
д е ж з
1001001/1011 0010011/1011 0100110/1011 0100111
1011 1011 1011
------ ------ ------ 1010011
1000 101 1010
1011 1011 1101001
------ ------
110 1
Рис. 1. Побудова циклічного коду і виправлення помилки.
2.2. Визначення і застосування циклічного надлишкового коду.
Розглянуті циклічні коди забезпечують виявлення і корекцію помилок, однак це вимагає певних затрат (контрольна частина займає значну частину результуючого коду). В той же час при значній інтенсивності завад можливі багатократні і групові помилки для виявлення і виправлення яких потрібно збільшувати кількість контрольних розрядів та ускладнювати методи їх визначення. Тому у цьому випадку доцільно здійснювати тільки перевірку блоків переданої інформації і при наявності помилок не коректувати їх, а повторно передавати один або кілька блоків. Це може суттєво зменшити затрати часу. Варто зауважити, що при низькому рівні завад і відсутності помилок контрольна частина все одно передається, а при високому рівні завад контрольна частина не завжди забезпечує виявлення і корекцію помилок.
Елементарним методом виявлення непарної кількості помилок у байті є контроль парності та непарності, тобто підрахунок кількості одиничних розрядів і доповнення її до парної чи непарної з виділенням одного додаткового розряду для збереження значення доповнення. Хоча цей метод не забезпечує виявлення парної кількості помилок він широко застосовується (наприклад у протоколі RS-232C).
Для збільшення кількості виявлених помилок і забезпечення надійності передачі інформації використовуються більш складні методи. Найпоширенішим з них є застосування циклічного надлишкового коду (CRC). Визначення CRC базується на принципах побудови циклічних кодів і є різновидністю хешування, тобто відображенням множини розрядів інфор-маційного блоку (розміром 128-1024 байт) на меншу множину розрядів коду CRC (16 аба 32 біти). Очевидно, що при такому відображенні однакове значення CRC може відповідати кільком різним варіантам інформаційних блоків, однак імовірність перетворення одного варіанта блока в інший за рахунок спотворення кодів завадами є дуже малою.
Визначення CRC здійснюється так само як і визначення остачі в циклічних кодах. При цьому значення утворюючого полінома для CRC-16 береться x16+x15+x2+1 або 110000000000001012, а для CRC-32 – x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1 або 1000001001100000100011101101101112. Інколи використовуються і інші утворюючі поліноми. Значення CRC долучається до блоку інформації і передається у канал зв’язку. Після прийому отримана послідовність бітів ділиться на утворюючий поліном і здійснюється контроль переданої інформації на наявність помилок. При виявленні помилок (остача не рівна нулю) формується відповідний запит і спотворені завадами блоки передаються повторно.
З метою збільшення швидкодії визначення CRC може здійснюватися апаратурно на основі регістрів зсуву та суматорів по модулю 2 (операція XOR). Схема ділення на поліном для CRC-16 приведена на рис. 2.
Рис. 2. Апаратурне визначення CRC.
Приклад визначення циклічного надлишкового коду представлений на рис 3.
11100001011010110000000000000000/11000000000000101
11000000000000101
-------------------------
10000101101001100
11000000000000101
-------------------------
10001011010010010
11000000000000101
-------------------------
10010110100101110
11000000000000101
--------------------------
10101101001010110
11000000000000101
-------------------------
11011010010100110
11000000000000101
-------------------------
11010010100011000
11000000000000101
-------------------------
10010100011101000
11000000000000101
-------------------------
10101000111011010
11000000000000101
-------------------------
11010001110111110
11000000000000101
------------------------- Код для передачі по каналу зв’язку
Остача 100011101110110 1110000101101011100011101110110
Рис. 3. Визначення циклічного надлишкового коду.
2.3. Програмна реалізація методу циклічного кодування
Розглянемо можливий варіант програмної реалізації методу циклічного кодування. Цей варіант базується на використанні операцій зсуву, логічного множення та додавання, а також операціії XOR. З метою забезпечення високої швидкодії використовуються регістрові команди Асемблера. Для визначення CRC-16 використовуються двобайтові регістри, а для CRC-32 – чотирьохбайтові. Враховуючи те, що для збереження утворюючого полінома CRC-16 необхідно 17 двійкових розрядів, а для CRC-32 – 33 двійкових розряди алгоритм треба реалізувати таким чином, щоб не проводити операції XOR із старшим 16 чи 32 розрядом (розряди нумеруються починаючи з нульового справа). Для CRC-16 це здійснюється у наступний спосіб (рис4). Молодші 16 розрядів утворюючого полінома записуються у регістр BX. Регістр AX заповнюється двійковими розрядами інформаційного блоку (доповненого 16 нулями). При цьому здійснюється зсув вліво до тих пір поки старший розряд регістру AX не буде рівний одиниці (операції з незначущими нулями . не проводяться). Потім здійснюється ще один зсув вліво і над вмістом регістру АХ (16 розрядів інформаційного блоку) і вмістом регістру ВХ (16 молодших розрядів утворюючого полінома) проводиться операція XOR. Результат операції XOR для зсунутого одиничного 17 розряду інформаційної частини та одиничного 17 розряду утворюючого полінома відомий і завжди рівний нулю. Якщо розряди інформаційного блоку ще не вичерпані, то знову здійснюється зсув вмісту регістра АХ вліво (з дозаписом нових розрядів інформаційного блоку справа). Якщо всі розряди інформаційного блоку (з дописаними 16 нулями) вичерпані, то в регістрі АХ отримаємо шукану остачу, яка і буде значенням CRC-16. Отримане значення CRC-16 дописується до інформаційного блоку замість 16 нулів і отримана послідовність бітів передається у канал зв’язку.
1 1 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 000000000000
1
1
0
0
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0
Рис. 4.
КОНТРОЛЬНІ ЗАПИТАННЯ
На чому базуються виявляючі та коректуючі властивості циклічних кодів?
Яку роль грає залишок при побудові та використанні циклічного коду?
Вкажіть роль утворюючого полінома та його властивості.
Яка різниця між циклічним кодом і циклічним надлишковим кодом?
Як впливає розмір блока на виявляючі властивості циклічного надлишкового коду.
ЛАБОРАТОРНЕ ЗАВДАННЯ
Ознайомтесь з методом побудови циклічних кодів.
Для заданого варіанту побудуйте циклічний код, внесіть, виявіть і виправте помилку, а також визначте CRC-16 вручну.
Розробiть алгоритм і програму побудови циклічних кодів та визначення CRC-16.
Реалiзуйте програму перевiрки та виправлення кодових послiдовностей.
Перевiрте роботоздатнiсть програм на тестових прикладах.
ОФОРМЛЕННЯ ЗВІТУ
Короткий опис методу та алгоритму побудови циклічних кодів.
Опис методу та алгоритму перевiрки та виправлення кодових послiдовностей.
Результати побудови циклічних кодів та визначення CRC-16 вручну.
Тексти програм.
Результати тестування програм.
6. ЛІТЕРАТУРА
Цымбал В.П. Теория информации и кодирование.: - К.: Вища школа, 1992.
Лагутенко О.И. Модемы. Справочник пользователя.: - СПб. Лань, 1997.
ІНДИВІДУАЛЬНІ ЗАВДАННЯ
Варіант
Інформаційна частина
Утворюючий поліном
1
1000
1101
2
1001
1101
3
1010
1101
4
1011
1101
5
1100
1101
6
1110
1101
7
1111
1101
8
1100
1101
9
0101
1101
10
0110
1101
11
0111
1101
12
0010
1101
13
0011
1101
14
0001
1101
15
0001
1101
16
0010
1011
17
0011
1011
18
0100
1011
19
0101
1011
20
0110
1011
21
0111
1011
22
1000
1011
23
1001
1011
24
1010
1011
25
1100
1011
26
1101
1011
27
1110
1011
28
1111
1011
НАВЧАЛЬНЕ ВИДАННЯ
ЦИКЛІЧНІ КОДИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи з курсу
“Проблемно-орієнтовані методи та засоби інформаційних технологій”
для студентів базового напрямку 6.0305 “Філологія”.
Укладач Мазур Віталій Володимирович
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора