ЦИКЛІЧНІ КОДИ. Звіт до лабораторної роботи з Методи та засоби комп’ютерних інформаційних технологій. Робота № 519998

Перехід до торгівельного партнера Binance

ЦИКЛІЧНІ КОДИ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2008

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Методи та засоби комп’ютерних інформаційних технологій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР ЗВІТ до лабораторної роботи №5 з курсу: „Методи та засоби комп’ютерних інформаційних технологій” на тему: „ ЦИКЛІЧНІ КОДИ” МЕТА РОБОТИ Мета роботи - вивчення метод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. Визначення циклічного надлишкового коду. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Варіант Інформаційна частина Утворюючий поліном 7 1111 1101 ТЕКСТ ПРОГРАМИ: title lab6 sseg segment stack db 256 dup(?) sseg ends dseg segment mes0 db 'TO CODE-0,TO CHECK-1:$' mes1 db 0D,0Ah,'FILE NAME:$' filein db 15 dup(?),0 fid dw ? error db 0Dh,0Ah,'CAN`T OPEN FILE!$' buffer db 60000 dup(?) bsize dw ? mes2 db 0Dh,0Ah,'FINISH$' mes3 db 0Dh,0Ah,'NO MISTAKES$' mes4 db 0Dh,0Ah,'IS MISTAKES$' poly dw 1000000000000101b dseg ends cseg segment assume ss:sseg,ds:dseg,cs:cseg start: jmp main main: push ds xor ax,ax push ax mov ax,dseg mov ds,ax mov ah,09h mov dx,offset mes0 int 21h mov ah,10h int 16h cmp al,31h jne begin call check jmp exit begin: call infile mov si,0 c2: mov al,filein[si] cmp al,2Eh je e2 inc si jmp c2 e2: inc si mov al,6Dh mov filein[si],al inc si mov al,75h mov filein[si],al inc si mov al,73h mov filein[si],al mov ah,5Bh mov cx,0 mov dx,offset filein int 21h jc er mov fid,ax mov ah,40h mov bx,fid mov cx,bsize mov dx,offset buffer int 21h call coding mov ah,40h mov bx,fid mov cx,2 mov dx,offset buffer int 21h call fclose mov ah,09h mov dx,offset mes2 int 21h jmp exit er: mov ah,09h mov dx,offset error int 21h exit: mov ah,10h int 16h mov ax,4C00h int 21h infile proc near mov ah,09h mov dx,offset mes1 int 21h mov di,0 c1: mov ah,01h int 21h cmp al,0Dh je e1 mov filein[di],al inc di jmp c1 e1: mov ah,3Dh mov al,0 mov dx,offset filein int 21h jc er mov fid,ax mov ah,3Fh mov bx,fid mov cx,60000 mov dx,offset buffer int 21h mov bsize,ax call fclose ret infile endp ralb proc near mov si,bsize dec si cl1: mov al,buffer[si] rcl al,1 mov buffer[si],al pushf dec si cmp si,-1 je el1 popf jmp cl1 el1: popf ret ralb endp coding proc near mov cx,bsize d1: push cx mov cx,8 dd1: push cx call ralb jnc f1 mov ah,buffer[0] mov al,buffer[1] xor ax,poly mov buffer[0],ah mov buffer[1],al f1: pop cx dec cx cmp cx,0 jne dd1 pop cx dec cx cmp cx,0 jne d1 ret coding endp fclose proc near mov ah,3Eh mov bx,fid int 21h ret fclose endp check proc near call infile call coding mov ah,buffer[0] mov al,buffer[1] cmp ax,0 jne ch1 mov ah,09h mov dx,offset mes3 int 21h jmp qu ch1: mov ah,09h mov dx,offset mes4 int 21h qu: ret check endp cseg ends end start Висновки. На даній лабораторній роботі я вивчила методи завадостійкого кодування (циклічні коди) та особливості їх програмної і апаратурної реалiзацiї.

Звіт до лабораторної роботи Методи та засоби комп’ютерних інформаційних технологій

infoman

10.02.2013 23:02-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись