Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Циклічні коди
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2005
Тип роботи:
Звіт
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН-313
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
“ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Звіт
до лабораторної роботи №4
з курсу :
“ Методи та засоби комп’ютерних інформаційних технологій ”
на тему :
“ Циклічні коди ”
Варіант №20
Мета роботи - вивчення методiв завадостійкого кодування (циклічні коди) та особливостей їх програмної і апаратурної реалiзацiї.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Побудова і застосування циклічних кодів.
Коди називаються циклічними, якщо частина чи всі дозволені кодові комбінації для них можуть бути отримані шляхом циклічного зсуву однієї або кількох комбінацій. Циклічний зсув здійснюється справа наліво, причому крайній лівий символ переноситься в кінець комбінації. Циклічні коди відносяться до лінійних блочних кодів.
Побудова циклічних кодів базується на використанні неприводимих у полі двійкового числа поліномів. Неприводимі поліноми діляться без остачі тільки на себе і на одиницю.
Для отримання циклічного коду для заданої комбінації інформаційних бітів (наприклад, 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 – контрольна .
Для знаходження і виправлення помилок в циклічних кодах отримані після передачі по каналу зв’язку комбінації діляться на утворюючий поліном для знаходження остачі. При діленні для бітів використовується не віднімання, а операція XOR. Циклічний зсув отриманої комбінації і ділення на утворюючий поліном здійснюють до тих пір поки кількість одиниць в остачі буде менша або рівна значенню коректуючої властивості коду (в нашому випадку виявляється і коректується одна помилка у коді). При цьому, якщо остача рівна нулю, то кодова комбінація правильна, а якщо не рівна нулю, то сума (по модулю 2) остачі з отриманою кодовою комбінацією дасть правильну кодову комбінацію.
Утворюючий поліном відповідної степені вибирається з таблиць, приведених в літературі, на основі відомої довжини інформаційної частини коду. Наприклад для інформаційної частини довжиною чотири біти утворюючий поліном має степінь 3 і може приймати значення 1011 або 1101. Для позначення кодів використовується пара (j.k), де: j – загальна довжина коду, а k – довжина контрольної частини (наприклад (7.3)).
Визначення і застосування циклічного надлишкового коду.
Розглянуті циклічні коди забезпечують виявлення і корекцію помилок, однак це вимагає певних затрат (контрольна частина займає значну частину результуючого коду). В той же час при значній інтенсивності завад можливі багатократні і групові помилки для виявлення і виправлення яких потрібно збільшувати кількість контрольних розрядів та ускладнювати методи їх визначення. Тому у цьому випадку доцільно здійснювати тільки перевірку блоків переданої інформації і при наявності помилок не коректувати їх, а повторно передавати один або кілька блоків. Це може суттєво зменшити затрати часу. Варто зауважити, що при низькому рівні завад і відсутності помилок контрольна частина все одно передається, а при високому рівні завад контрольна частина не завжди забезпечує виявлення і корекцію помилок.
Елементарним методом виявлення непарної кількості помилок у байті є контроль парності та непарності, тобто підрахунок кількості одиничних розрядів і доповнення її до парної чи непарної з виділенням одного додаткового розряду для збереження значення доповнення. Хоча цей метод не забезпечує виявлення парної кількості помилок він широко застосовується (наприклад у протоколі 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. Визначення циклічного надлишкового коду.
Текст програми.(Циклічні коди)
#include<stdio.h>
#include <conio.h>
int rar(int x);
int bit(int p);
main()
{
int a[7],i,j,i1,n1,n,p,k,r,t,z;
i=0;
printf("\n\nEnter 4 information bits: ");
for(j=0;j<4;j++){
scanf("%d",&z);
i=i<<1;
i=i+z;
}
n=0;
printf("\n\nEnter polinom (4 bits): ");
for(j=0;j<4;j++){
scanf("%d",&z);
n=n<<1;
n=n+z;}
n1=n;
i=i<<3;
i1=i;
k=1;
while(k>=0){
n=n1;
k=bit(i);
k=k-4;
n=n<<k;
i=i^n;
}
i1=i1+i;
printf("\nCode infirmation bits: ");
r=i1;
for(j=0;j<7;j++){
if(i1%2) a[j]=1;
else a[j]=0;
i1=i1>>1;}
for(j=6;j>-1;j--) printf("%d ",a[j]);
printf("\nEnter error in code : ");
i=0;
for(j=0;j<7;j++){
scanf("%d",&z);
i=i<<1;
i=i+z;}
i1=i;
if (r!=i1)
{
t=0;
i=0;
while(i!=1){
i=i1;
k=1;
while(k>=0){
n=n1;
k=bit(i);
k=k-4;
n=n<<k;
i=i^n;
}
i1=rar(i1);
t=t+1;
}
for(j=0;j<6;j++) i1=rar(i1);
printf("\nNumber of error bit : %d\n",t-1);
if(i1%2) i1=i1-1;
else i1=i1+1;
t=8-t;
for(j=0;j<t;j++) i1=rar(i1);
printf("\nCorrected code : ");
for(j=0;j<7;j++){
if(i1%2) a[j]=1;
else a[j]=0;
i1=i1>>1;}
for(j=6;j>-1;j--) printf("%d ",a[j]);
}
else printf("\n No errors!");
getch();
}
int rar(int x)
{
if(x%2) {x=x>>1; x=x+64;}
else x=x>>1;
return x;
}
int bit(int p)
{
int k;
k=0;
while (p){
p=p>>1;
k=k+1;}
return k; }
Текст програми.(CRC коди)
program laba4_2;
uses crt;
type W=array[1..20] of byte;
var infbit:array[1..4] of byte;
pol:array[1..17] of byte;
Inf,temp:W;
i,j,z,k,n:integer;
zal,h:boolean;
zav:integer;
procedure rah(var h:boolean);
begin
h:=false;
repeat
j:=1;
for i:=1 to 20 do write(' ',temp[i]);
writeln;
while temp[j]<>1 do inc(j);
if j+16<20 then
begin
writeln('+');
for i:=1 to j-1 do write(' ');
for i:=1 to 17 do write(' ',pol[i]);
writeln;
for i:=1 to 17 do
begin
if temp[j]=pol[i] then temp[j]:=0 else temp[j]:=1;
j:=j+1;
end;
end
else break
until h=true;
end;
begin
clrscr;
z:=0;
writeln('vvedit informaciini bitu');
writeln(' ');
for i:=1 to 4 do
begin
read (infbit[i]);
end;
write('code:');
pol[1]:=1;
pol[2]:=1;
pol[15]:=1;
pol[16]:=0;
pol[17]:=1;
for i:=1 to 4 do
begin
Inf[i]:=Infbit[i];
end;
for i:=5 to 20 do Inf[i]:=0;
for i:=3 to 14 do pol[i]:=0;
for i:=1 to 20 do
begin
temp[i]:=inf[i];
{write(temp[i]);}
end;
writeln(' ');
for i:=1 to 20 do write(inf[i]);
writeln;
writeln;
{----------------------------------------------------------}
writeln(' ');
h:=false;
rah(h);
writeln;
writeln('zagalnui kod :');
writeln(' ');
for i:=1 to 20 do write(' ',temp[i]);
writeln;
writeln('+');
for i:=1 to 20 do write(' ',inf[i]);
writeln;
for i:=1 to 20 do
if temp[i]=inf[i] then temp[i]:=0 else temp[i]:=1;
for i:=1 to 20 do write(' ',temp[i]);
writeln;
{-----------------------------------------------------------------------}
writeln('vvedit pomulkovui bit');
writeln(' ');
read(zav);
if temp[21-zav]=1 then temp[21-zav]:=0 else temp[21-zav]:=1;
writeln('Pomulkovui sygnal: ');
writeln(' ');
readln;
for i:=1 to 20 do write(temp[i]);
readln;
writeln;
writeln('perevirka sugnaly');
writeln(' ');
rah(h);
for i:=1 to 20 do
if temp[i]=1 then
begin
z:=1;
n:=i;
end;
if z=1 then writeln('Pomulka v',21-n,' biti');
writeln(' ');
readln;
end.
Виконання індивідуального завдання
Інформаційна частина 0110
Утворюючий поліном 1011
0110000/1011 0110001/1011 0010001/1011 0100010/1011
1011 1011 1011 1011
------ -------- -------- ---------
1101 1110 00111 001110
1011 1011 1011 1011
-------- -------- ------ ------
1100 1011 1100 0101
1011 1011
-------- -------
01110 0000
1011
------
1010
1011
------
0001
1000100/1011
1011
--------
0111
1011
--------
1100
1011
------
1110 1000101
1011 1100010
------ 0110001
01010
1011
------
0001
Визначення CRC-16
01100000000000000000/11000000000000101
11000000000000101
-------------------------
10100000000000101
11000000000000101
---------------------------
11000000000000000
11000000000000101
---------------------------
000000000000001010
11000000000000101
-----------------------------
11000000000001111
11000000000000101
---------------------------
000000000000010100
11000000000000101
-----------------------------
11000000000010001
11000000000000101
---------------------------
00000000000010100
Код для передачі по каналу зв’язку 011010100
Висновок: на цій лабораторній роботі я вивчив методи завадостійкого кодування (циклічні коди) та особливості їх програмної і апаратурної реалізіції.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора