Шпаргалка

Шпаргалка на тему Построение циклических кодов

Работа добавлена на сайт bukvasha.net: 2015-06-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 2.4.2025


§ 1 Введение

Код ,в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим ( полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.

Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.

В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет свести действия над кодовыми комбинациями к действием над многочленами (используя аппарат полиномиальной алгебры).

Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике.

Циклические коды используются в ЭВМ при последовательной передаче данных .

2 Постановка задачи

Построить циклический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки ( n=31 ,s=1) двумя

способами.

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

3 Операции над циклическими кодами

1. Сдвиг справа налево осуществляется путем умножения полинома на x:

G(x)=x4+x2+1 Û 0010101;

G(x)× x=x5+x3+x Û 0101010.

2. Операции сложения и вычитания выполняются по модулю 2 .

Они являются эквивалентными и ассоциативными :

G1(x)+G2(x)=>G3(x);

G1(x) -G2(x)=>G3(x);

G2(x)+G1(x)=>G3(x);

Пример:

G1(x)= x5 +x3+x;

G2(x)=x4 +x3 +1;

G3(x)=G1(x) Å G2(x) = x5 +x4+x+1.

3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложеное по модулю 2 :

G1(x)=x6+x4+x3 ;

G2(x)=x3+x2+1 .

4 Принцип построения циклических кодов

Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней ,т.е. такой многочлен делиться только на самого себя или на единицу и не делиться ни на какой другой многочлен. На такой многочлен делиться без остатка двучлен xn+1.Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Чтобы понять принцип построения циклического кода, умножаем комбинацию простого k-значного кода Q(x) на одночлен xr ,а затем делим на образующий полином P(x) , степень которого равна r. В результате умножения Q(x) на xr степень каждого одночлена, входящего в Q(x), повышается на r. При делении произведения xrQ(x) на образующий полином получается частное C(x) такой же степени, как и Q(x).

Частное C(x) имеет такую же степень, как и кодовая комбинация Q(x) простого кода, поэтому C(x) является кодовой комбинацией этого же простого k-значного кода. Следует заметить, что степень остатка не может быть больше степени образующего полинома, т.е. его наивысшая степень может быть равна (r-1). Следовательно, наибольшее число разрядов остатка R(x) не превышает числа r.

Умножая обе части равенства (1) на P(x) и произведя некоторые перестановки получаем :

F(x) = C(x) P(x) = Q(x) xr + R(x) (2)

Таким образом, кодовая комбинация циклического n-значного кода может

быть получена двумя способами:

1) умножение кодовой комбинации Q(x) простого кода на одночлен xr

и добавление к этому произведению остатка R(x) , полученного в результате деления произведения Q(x) xr на образующий полином P(x);

2) умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).

При построении циклических кодов первым способом расположение информационных символов во всех комбинациях строго упорядочено - они занимают k старших разрядов комбинации, а остальные (n-k) разрядов отводятся под контрольные.

При втором способе образования циклических кодов информационные и контрольные символы в комбинациях циклического кода не отделены друг от друга, что затрудняет процесс декодирования.

6. Разработка текста программы

Для представления информационного слова в памяти используется

массив. В состав программы входит основная программа и два модуля,

реализующие алгоритм кодирования и декодирования информационных слов и диалога с пользователем соответственно.

Program Cyclic_Code;

Uses

Crt,_CC31,_Serv;

Var

m,mm:Move_code;

p:Polinom;

r:Rest;

i,Mainflag,From,Error:integer;

Switch:byte;

Key:boolean;

begin

Repeat

Key:=true;

TextColor(11);

TextBackGround(7);

Clrscr;

SetWindow(24,10,45,14,2,' Главное меню ');

Switch:=GetMainMenuChoice;

case Switch of

1:begin

About;

Readln;

Key:=False;

end;

2: begin

TextColor(0);

ClrScr;

SetWindow(25,10,40,13,1,' Образовать ');

Switch:=GetSubMenuChoice;

case Switch of

1:begin

TextBackGround(0);

TextColor(15);

ClrScr;

SetWindow(1,1,79,24,2,' Демонстрация');

TextColor(14);

 

GotoXY(2,2);

Init(m,p,r,MainFlag);

Write(‘Информационный полином ');

TextColor(2);

for i:=n downto 0 do

begin

if(i=0)and(r2[i1]=0))do dec(i1);

if(i1=-1)then goto RETURN;

Kol:=n1-i1;

while(Kol>0)do

begin

for i:=n1 downto 1 do

r2[i]:=r2[i-1];

dec(Kol);

end;

Kol:=n1-i1;

while((Kol>0)and(j>=0))do

begin

r2[Kol-1]:=m2[j];

dec(Kol);

dec(j);

end;

if((j=-1)and(Kol=0))

then begin

for i:=n1 downto 0 do

r2[i]:=r2[i] xor p2[i];

end

else flag:=Kol;

end;

end

else if(n1=j)

then begin

for i:=n1 downto 0 do

begin

r2[i]:=m2[j];

dec(j);

end;

for i:=n1 downto 0 do

r2[i]:=r2[i] xor p2[i]

end

else if(j0)then

begin

k:=n1-flag;

for i:=n1 downto flag do

begin

m3[k]:=r3[i];

dec(k);

end;

end

 

 

else begin

for i:=n1-1 downto 0 do

m3[i]:=r3[i];

end;

end;

Procedure MakeError(var m4:Move_code;var err:integer);

begin

Randomize;

err:=Random(n);

m4[err]:=m4[err] xor 1;

end;

Procedure Decoder(var m6:Move_Code);

var

i:integer;

k:byte;

begin

k:=5;

while(k>0) do

begin

for i:=0 to n-1 do

m6[i]:=m6[i+1];

dec(k);

end;

for i:=n downto n-n1+1 do

m6[i]:=0;

end;

Procedure BildMoveCodeMultiplication(var m7:Move_Code);

var

m1,m2,m3,m4,mm:Move_Code;

i,j:integer;

begin

mm:=m7;

m1:=m7;

for j:=0 to 1 do

begin

for i:=n downto 1 do

m1[i]:=m1[i-1];

m1[j]:=0;

end;

m2:=m7;

for j:=0 to 2 do

begin

for i:=n downto 1 do

m2[i]:=m2[i-1];

m2[j]:=0;

end;

m3:=m7;

for j:=0 to 3 do

begin

for i:=n downto 1 do

m3[i]:=m3[i-1];

m3[j]:=0;

end;

m4:=m7;

for j:=0 to 4 do

begin

for i:=n downto 1 do

m4[i]:=m4[i-1];

m4[j]:=0;

end;

for i:=n downto 0 do

m7[i]:=mm[i] xor m1[i]xor m2[i]xor m3[i] xor m4[i];

end;

Procedure Correction(var m5:Move_code;p5:Polinom;var r5:Rest);

var

i,Correctflag,i1:integer;

Count,Countcarry,Carryflag:byte;

begin

Correctflag:=0;

Countcarry:=0;

repeat

for i:=n1 downto 0 do

r5[i]:=0;

Count:=0;

Divizion(m5,r5,p5,Correctflag);

i1:=n1;

while((i1>=Correctflag)and(r5[i1]=0))do dec(i1);

if({(i1=Correctflag-1) or

(}(i1=Correctflag)and(r5[Correctflag]=1)){)}

then m5[0]:=m5[0] xor r5[Correctflag]

else begin

Carryflag:=m5[n];

for i:=n downto 1 do

m5[i]:=m5[i-1];

m5[0]:=Carryflag;

inc(Countcarry);

end;

until ({(i1=Correctflag-1) or

(}(i1=Correctflag)and(r5[Correctflag]=1));{);}

while (Countcarry>0) do

begin

Carryflag:=m5[0];

for i:=0 to n-1 do

m5[i]:=m5[i+1];

m5[n]:=Carryflag;

dec(Countcarry);

end;

end;

end.

 

 

 

 

Приложение № 2

Процедуры и функции модуля _Serv.

Unit _SERV;

Interface

Uses

Crt,Dos;

Const

EmptyBorder =0;

SingleBorder =1;

DoubleBorder =2;

BorderChar:array[0..2,1..6] of Char=

((#32,#32,#32,#32,#32,#32),

(#218,#196,#191,#179,#192,#217),

(#201,#205,#187,#186,#200,#188));

MaxChar=80;

MaxLine=25;

MenuTop=3;

SubMenuTop =2;

MenuLine :array[1..MenuTop]of string[20]=

(' О программе...',' Демонстрация ' ‘Выход ');

SubMenuLine :array[1..SubMenuTop]of string[20]=

(' Сложением' , ' Умножением');

Procedure SetWindow(x1,y1,x2,y2,Bord:byte;Header:string);

Procedure CursorOff;

Function GetMainMenuChoice:byte;

Function GetSubMenuChoice:byte;

Procedure About;

Implementation

Procedure SetWindow(x1,y1,x2,y2,Bord:byte;Header:string);

var

i:integer;

begin

if not ((x11)

then dec(Count);

#80 : if(Count1)

then dec(Count);

#80 : if(Count


1. Реферат на тему Term Limits In US Government Essay Research
2. Реферат Поэтика древнерусской литературы
3. Контрольная работа Трудовые затраты как потенциальная будущая выгода предприятия
4. Изложение Фёдор Абрамов. Алька
5. Реферат на тему A Seize Of Power Essay Research Paper
6. Курсовая на тему Финансовый леверидж
7. Курсовая на тему Понятие и основания возникновения материальной ответственности сто
8. Реферат Информация. Информационные процессы
9. Реферат СІЛЬСКЕ ГОСПОДАРСТВО УКРАІНИ У 50-Х - 60Х РОКАХ
10. Реферат на тему Friendships Essay Research Paper Life is more