Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЦИКЛІЧНІ КОДИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Проблемно-орієнтовані методи та засоби інформаційних технологій
Група:
КН-316
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
ЗВІТ
про виконання лабораторної роботи №5
на тему:
«ЦИКЛІЧНІ КОДИ»
з курсу:
“Проблемно-орієнтовані методи та засоби інформаційних технологій”
МЕТА РОБОТИ
Мета роботи - вивчення методiв завадостійкого кодування (циклічні коди) та особливостей їх програмної і апаратурної реалiзацiї.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Визначення і застосування циклічного надлишкового коду.
Розглянуті циклічні коди забезпечують виявлення і корекцію помилок, однак це вимагає певних затрат (контрольна частина займає значну частину результуючого коду). В той же час при значній інтенсивності завад можливі багатократні і групові помилки для виявлення і виправлення яких потрібно збільшувати кількість контрольних розрядів та ускладнювати методи їх визначення. Тому у цьому випадку доцільно здійснювати тільки перевірку блоків переданої інформації і при наявності помилок не коректувати їх, а повторно передавати один або кілька блоків. Це може суттєво зменшити затрати часу. Варто зауважити, що при низькому рівні завад і відсутності помилок контрольна частина все одно передається, а при високому рівні завад контрольна частина не завжди забезпечує виявлення і корекцію помилок.
Елементарним методом виявлення непарної кількості помилок у байті є контроль парності та непарності, тобто підрахунок кількості одиничних розрядів і доповнення її до парної чи непарної з виділенням одного додаткового розряду для збереження значення доповнення. Хоча цей метод не забезпечує виявлення парної кількості помилок він широко застосовується (наприклад у протоколі 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. Визначення циклічного надлишкового коду.
Програмна реалізація методу циклічного кодування
Розглянемо можливий варіант програмної реалізації методу циклічного кодування. Цей варіант базується на використанні операцій зсуву, логічного множення та додавання, а також операціії 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
Текст програми створення CRC:
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <conio.h>
#include <iostream>
#ifndef ___CRC16_H___
#define ___CRC16_H___
void crc16_init(unsigned short *uCrc16);
void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize);
void crc16_final(unsigned short *uCrc16);
void crc16ccitt_init(unsigned short *uCcitt16);
void crc16ccitt_update(unsigned short *uCcitt16, unsigned char *pBuffer, unsigned long uBufSize);
void crc16ccitt_final(unsigned short *uCcitt16);
#endif // ___CRC16_H___
using namespace System;
int main(array<System::String ^> ^args)
{
Console::WriteLine(L"Hello World");
//System::String^ filename = "";
FILE *fp = NULL;
FILE *fc = NULL;
unsigned long uRead = 0;
unsigned short m_crc16;
unsigned char pBuf[16384];
String ^s1;
String ^flnm;
fp = fopen("c:\\mzkit\\bdn\\lab5\\test.txt" , "rb");
fc = fopen("c:\\mzkit\\bdn\\lab5\\checksum.bin", "w+");
uRead = fread(pBuf, 1, 16384, fp);
crc16_init(&m_crc16);
crc16_update(&m_crc16, pBuf, uRead);
crc16_final(&m_crc16);
printf("CheckSumm : %04X", m_crc16,"\n");
fwrite(&m_crc16,2,1,fc);
fclose(fc);
getche();
return 0;
}
//#include "crc16.h"
static const unsigned short crc16tab[] = /* CRC lookup table */
{
0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};
void crc16_init(unsigned short *uCrc16)
{
*uCrc16 = 0xFFFF;
}
void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize)
{
unsigned long i = 0;
for(i = 0; i < uBufSize; i++)
*uCrc16 = (*uCrc16 >> 8) ^ crc16tab[(*uCrc16 ^ *pBuffer++) & 0xFF];
}
void crc16_final(unsigned short *uCrc16)
{
*uCrc16 = ~(*uCrc16);
}
void crc16ccitt_init(unsigned short *uCcitt16)
{
*uCcitt16 = 0xFFFF;
}
void crc16ccitt_update(unsigned short *uCcitt16, unsigned char *pBuffer, unsigned long uBufSize)
{
unsigned int i = 0;
for(i = 0; i < uBufSize; i++)
{
*uCcitt16 = (*uCcitt16 >> 8) | (*uCcitt16 << 8);
*uCcitt16 ^= pBuffer[i];
*uCcitt16 ^= (*uCcitt16 & 0xFF) >> 4;
*uCcitt16 ^= (*uCcitt16 << 8) << 4;
*uCcitt16 ^= ((*uCcitt16 & 0xFF) << 4) << 1;
}
}
void crc16ccitt_final(unsigned short *uCcitt16)
{
*uCcitt16 = ~(*uCcitt16);
}
Текст програми перевірки CRC:
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <conio.h>
#include <iostream>
#ifndef ___CRC16_H___
#define ___CRC16_H___
void crc16_init(unsigned short *uCrc16);
void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize);
void crc16_final(unsigned short *uCrc16);
void crc16ccitt_init(unsigned short *uCcitt16);
void crc16ccitt_update(unsigned short *uCcitt16, unsigned char *pBuffer, unsigned long uBufSize);
void crc16ccitt_final(unsigned short *uCcitt16);
#endif // ___CRC16_H___
using namespace System;
int main(array<System::String ^> ^args)
{
Console::WriteLine(L"Hello World");
//System::String^ filename = "";
FILE *fp = NULL;
FILE *fc = NULL;
unsigned long uRead = 0;
unsigned short m_crc16;
unsigned char pBuf[16384];
String ^s1;
String ^flnm;
unsigned short p_crc16;
fp = fopen("c:\\mzkit\\bdn\\lab5\\test.txt" , "rb");
fc = fopen("c:\\mzkit\\bdn\\lab5\\checksum.bin", "rb");
uRead = fread(pBuf, 1, 16384, fp);
fread(&p_crc16,2,1,fc);
crc16_init(&m_crc16);
crc16_update(&m_crc16, pBuf, uRead);
crc16_final(&m_crc16);
//printf(" ", p_crc16, " ", m_crc16);
if (m_crc16 != p_crc16)
printf("error");
else
printf("correct");
getche();
return 0;
}
//#include "crc16.h"
static const unsigned short crc16tab[] = /* CRC lookup table */
{
0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};
void crc16_init(unsigned short *uCrc16)
{
*uCrc16 = 0xFFFF;
}
void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize)
{
unsigned long i = 0;
for(i = 0; i < uBufSize; i++)
*uCrc16 = (*uCrc16 >> 8) ^ crc16tab[(*uCrc16 ^ *pBuffer++) & 0xFF];
}
void crc16_final(unsigned short *uCrc16)
{
*uCrc16 = ~(*uCrc16);
}
void crc16ccitt_init(unsigned short *uCcitt16)
{
*uCcitt16 = 0xFFFF;
}
void crc16ccitt_update(unsigned short *uCcitt16, unsigned char *pBuffer, unsigned long uBufSize)
{
unsigned int i = 0;
for(i = 0; i < uBufSize; i++)
{
*uCcitt16 = (*uCcitt16 >> 8) | (*uCcitt16 << 8);
*uCcitt16 ^= pBuffer[i];
*uCcitt16 ^= (*uCcitt16 & 0xFF) >> 4;
*uCcitt16 ^= (*uCcitt16 << 8) << 4;
*uCcitt16 ^= ((*uCcitt16 & 0xFF) << 4) << 1;
}
}
void crc16ccitt_final(unsigned short *uCcitt16)
{
*uCcitt16 = ~(*uCcitt16);
}
Висновок: на даній лабораторній роботі я вивчив методи завадостійкого кодування (циклічні коди) та особливості їх програмної і апаратної реалiзацiї.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора