Размещено на http://www.allbest.ru

Министерство образования и науки Республики Казахстан

Восточно Казахстанский технический университет имени Д.Серикбаева

Факультет базовой инженерной подготовки

Кафедра математического и компьютерного моделирования

КУРСОВАЯ РАБОТА

по дисциплине «Теория информации и кодирования»

на тему : «Циклические коды»

Выполнил: студент группы 18-МКК-2

Амангелдинов Э.Ж

Проверила:Тезекпаева Ш.Т

Усть-Каменогорск, 2021 год



Аннотация

Документа содержит описание программы, которая строит кодовые комбинации на основеа циклических кодов. Программа кодируета и декодирует информационные слова. Иммитируется работа источника, передающего информационное слово, кодировщика, кодирующего данное слово, канала связи и декодировщика, обнаруживающего и исправляющего ошибки в информационнома полиноме. Программа работаета по принципу приёмник - источник, так, как это реализовано в устройствах, передающих информациюа или обыкновенных приводаха для внешних носителей в PC.



Содержание

Аннотация

Введение

1. Циклические коды

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

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

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

4.1 Получение кодовой комбинации добавлением остатка R(x)

4.2Получение кодовой комбинации умножением на образующий полином

5. Разработка схемы алгоритма

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

7. Результаты работы программы

Выводы

Литература

Введение

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

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

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

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

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

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



1. Циклические коды

циклический код алгоритм умножение

Циклический код -- линейный, блочный кода, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок

Алгебраическое описание

Если {\displaystyle {\overrightarrow {c_{1}}}}а -- кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова {\displaystyle {\overrightarrow {c}}}а, то соответствующий ему полином {\displaystyle c_{1}(x)}а получается из предыдущего умножением на x:

{\displaystyle c_{1}(x)=xc(x)\mod (x^{n}-1)}а, пользуясь тем, что {\displaystyle x^{n}\equiv 1\mod (x^{n}-1).}

Сдвиг вправо и влево соответственно на {\displaystyle j}а разрядов:

{\displaystyle c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),}

{\displaystyle c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).}

Если {\displaystyle m(x)}а -- произвольный полином над полем {\displaystyle GF(q)}а, и {\displaystyle c(x)}а -- кодовое слово циклического {\displaystyle (n,k)}а кода, то {\displaystyle m(x)c(x)\mod (x^{n}-1)}а -- тоже кодовое слово этого кода.

Порождающий полином

Определение

Порождающим полиномом циклического {\displaystyle (n,k)} кода {\displaystyle C}а называется такой ненулевой полином {\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}} из {\displaystyle C}а, степень которого наименьшая, и коэффициент при старшей степени {\displaystyle g_{r}=1}а.

Теорема 1

Если {\displaystyle C}а -- циклический {\displaystyle (n,k)}а код, и {\displaystyle g(x)}а -- его порождающий полином, то степень {\displaystyle g(x)}а равна {\displaystyle r=n-k}а, и каждое кодовое слово может быть единственным образом представлено в виде

{\displaystyle c(x)=m(x)g(x),}

где степень {\displaystyle m(x)}аменьше или равна {\displaystyle k-1}а.

Теорема 2

{\displaystyle g(x)}а -- порождающий полином циклического {\displaystyle (n,k)}а кода -- является делителем двучлена {\displaystyle x^{n}-1}а.

Следствия

Таким образом, в качестве порождающего полинома можно выбирать любой полином делитель {\displaystyle x^{n}-1}а. Степень авыбранного полинома будет определять количество проверочных символов {\displaystyle r}а, число аинформационных символов {\displaystyle k=n-r}.

Порождающая матрица

Полиномы {\displaystyle g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)} линейно независимы, иначе {\displaystyle m(x)g(x)=0} при ненулевома {\displaystyle m(x)}, что невозможно.

Значит кодовые слова можно записывать, как и для линейных кодов, следующим образом:

{\displaystyle {\overline {m}}G=(m_{0},m_{1},\dots ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\\\dots \\x^{k-1}g(x)\end{bmatrix}}=m(x)g(x),}

где {\displaystyle G}а является порождающей матрицей, {\displaystyle m(x)} -- информационным полиномом.

Матрицу {\displaystyle G}а можно записать в символьной форме:

{\displaystyle G={\begin{bmatrix}g_{0}&g_{1}&\dots &g_{r-1}&g_{r}&0&\dots &0\\0&g_{0}&\dots &g_{r-2}&g_{r-1}&g_{r}&\dots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&\dots &0&g_{0}&g_{1}&\dots &g_{r}\end{bmatrix}}.}

Проверочная аматрица

Для каждого кодового слова циклического кода справедливо {\displaystyle c(x)=0\mod g(x)}а. Поэтому проверочную матрицу можно записать как

{\displaystyle H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).}а.

Тогда

{\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).}

Кодирование

Несистематическое

При несистематическом кодировании кодовоеа слово получается в виде произведения информационного полинома на порождающий:

{\displaystyle c(x)=m(x)g(x).}

Оно может быть реализовано при помощи перемножения полиномов.

Систематическоеа

При систематическом кодировании кодовое слово формируется в авиде информационного подблока и проверочного:

{\displaystyle c(x)=[s(x)\;m(x)].}а

Пусть информационное слово образует старшие степени кодового аслова, тогда

{\displaystyle c(x)=x^{r}m(x)+s(x),\quad r=n-k.}

Тогда из условия {\displaystyle c(x)=x^{r}m(x)+s(x)=0\mod g(x)} следуета

{\displaystyle s(x)=-x^{r}m(x)\mod g(x).}а

Это уравнение и задаёт правило систематического кодирования. Оно может а быть реализовано при помощи многотактных линейных афильтров (МЛФ).



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

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

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



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

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

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

G(x)F0D7x=x5+x3+x F0DB 0101010.

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

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) F0C5 G2(x) = x5 +x4+x+1.

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

G1(x)=x6+x4+x3 ; G2(x)=x3+x2+1 . x6+x4+x3 x3+x2+1

F0C5 x6+x5+x3 x3 +x2 x5 + x4 F0C5 x5 + x4 +x2

x2 то же в двоичном кодеа:

1011000 1101

F0C51101 1100

1100 F0C5 1101

100

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



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

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

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

Q(x) xr R(x)

F0BEF0BEF0BEF0BE = C(x) + F0BEF0BEF0BE , (1) P(x) P(x)

где R(x) - остатока от деления Q(x) xr на P(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-значного кода может быть получена двумя аспособами: умножение кодовой комбинации Q(x) простого кода на одночлен xr и добавление к этому произведению аостатка R(x) , полученного в результате деления произведения Q(x) xr на образующий полином P(x); умножения кодовой комбинации C(x) простого k-значного на образующий полином P(x).

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

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

4.1 Получение кодовой комбинации добавлением остатка R(x)

Построить циклический код для передачи 31 разрядной кодовой

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

Решение.

1. Определим число контрольных разрядова - m :

m = log2 (n+1) = log2 (31+1) = 5.

Определим количество информационных разрядова k :

k = n-m = 26,



т.е получили (31, 26 ) - код .

Строим информационный, а полином, соответствующий информационному слову длиной k-бит:

G(x)=00000000000000000000000101= x2 +1.

Осуществляем сдвиг кода влево на m=n-k=5 разрядов т.е полином G(x) умножается на xm:

xm G(x)= (x2+1) x5= x7+ x5 =0000000000000000000000010100000.

Выбирается образующий многочлен-P(x) по таблице неприводимых многочленов. Для исправления одиночной ошибки (d0=3) образующий полином P(x) должен быть степени

m=n-k=5

и количеством ненулевых членов не меньше минимального кодового расстояния d0 =3. Исходя из этого образующий полином P(x) равен :

P(x)= x5 + x4 +x3 +x 2 +1 = 111101.

Определим остаток R(x) от деления G(x)F0D7x m на образующий полином P(x)

x7+ x5 x5 + x4 +x3 +x 2 +1 10100000

111101

x7 + x6 +x5 +x 4 +x2 x2 +x +1 111101

111

x6 + x4 +x2 101010 x6 + x5 +x4 +x 3 +x 111101 x5 + x3 +x2 +x 101110 x5 + x4 +x3 +x 2 +1 111101 x4 +x +1 10011

Остаток

R(x)= x4+x+1 =10011.

Строим передаваемый кодовый пролином F(x) :

F(x)=xm G(x)F0C5R(x)= x7+ x5+ x4+x+1 =0000000000000000000000010110011.

Пусть в принятом сообщении произошла ошибка в тридцать первом разряде, при этом принятоеа кодовое сообщение имеет вид :

FF0A2(x)=F(x) F0C5 E(x)= 1000000000000000000000010110011.

Разделим многочлен F1(x) соответствующий полученной кодовой комбинации на образующий полином, при этома вес остатка (количество единиц в коде остатка) должена быть меньше или равен количеству ошибок W F0A3S

1000000000000000000000010110011 111101

111101

111010

111101

111000

111101

101000

111101

101010

111101

101110

111101

100110

111101

110110

111101

101100

111101

100010

111101

111110

111101

110010

111101

111111

111101

100011

111101 11110

Сравниваем вес полученного остатка w с числома исправляемых ошибок w>s

10. Производим циклический сдвиг принятой кодовой комбинации на один разряд влево и повторяем п.9 пока w F0A3 s.

a) 0000000000000000000000101100111 111101

111101

100011

111101

111101

111101 1 F0DE w=s .

Складываем по модулю 2 последнее делимое с последним остатком:

0000000000000000000000101100111

F0C5 1 0000000000000000000000101100110

Осуществляем обратный асдвиг на 1 разряд полученной комбинации

0000000000000000000000010110011

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

4.2 Построение кодовой комбинации путем умножения на образующий полином

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

Решение.

Строим информационный полином, ответствующий информационному слову длиной k-бит:

G(x)=00000000000000000000000101= x2 +2.

Строим передаваемый кодовый полином

00000000000000000000000101

111101

00000000000000000000000101

00000000000000000000000101

00000000000000000000000101

00000000000000000000000101

00000000000000000000000101

0000000000000000000000011001001



5. Разработка схемы алгоритма

Ciclic code

нет

да

нет да Конец



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<n-n1+1)then Textcolor(9);

Write(m[i]); end; TextColor(14);

GotoXY(2,3);

Write('Образующий полинома '); TextColor(13); for i:=n1 downto 0 do

Write(p[i]);

TextColor(14);

GotoXY(2,4);

Write('Сложениеа по модулю 2 (F(x)+P(x)): ');

FxPx(m);

TextColor(9); for i:=n downto 0 do begin

if(i<n1)then TextColor(2);

Write(m[i]); end; TextColor(14);

GotoXY(2,5);

Write('Остаток: ');

Divizion(m,r,p,Mainflag); TextColor(11);

for i:=n1 downto Mainflag do

Write(r[i]);

GotoXY(2,6);

TextColor(14);

Write('Передаваемый полином: ');

BildMoveCode(m,r,Mainflag);

TextColor(9); for i:=n downto 0 do

begin

if(i<n1) then TextColor(11);

Write(m[i]); end; GotoXY(2,7);

TextColor(14);

Write('Произошла ошибка... ');

MakeError(m,Error); TextColor(9); for i:=n downto 0 do begin

if(i=Error)then TextColor(12) else TextColor(9);

write(m[i]); end; GotoXY(2,8);

TextColor(14);

Write('Ошибка исправлена! ');

TextColor(9); Correction(m,p,r); for i:=n downto 0 do

begin

if(i=Error)then TextColor(10) else TextColor(9); write(m[i]); end; TextColor(14);

GotoXY(2,9);

Write('Исходный полином: ');

Decoder(m);

TextColor(2); for i:=n downto 0 do begin

if(i<n-n1+1)then Textcolor(9);

Write(m[i]); end; Key:=false; end; 2: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<n-n1+1)then Textcolor(9);

Write(m[i]); end; TextColor(14);

GotoXY(2,3);

Write('Образующий полином: '); TextColor(13); for i:=n1 downto 0 do

Write(p[i]);

TextColor(14);

GotoXY(2,4);

Write('Результат умножения: ');

BildMoveCodeMultiplication(m);

TextColor(9); for i:=n downto 0 do

Write(m[i]);

GotoXY(2,5);

TextColor(14);

Write('Произошла ошибка ... ');

MakeError(m,Error); TextColor(9); for i:=n downto 0 do begin

if(i=Error)then TextColor(12) else TextColor(9);

write(m[i]); end; GotoXY(2,6);

TextColor(14);

Write('Ошибка исправлена ! ');

TextColor(9); Correction(m,p,r); for i:=n downto 0 do begin

if(i=Error)then TextColor(10) else TextColor(9); write(m[i]); end; Key:=false; end;

end;

TextColor(14);

GotoXY(2,22);

Write('Нажмите любую клавишу...'); Readln; end; 3:begin

ClrScr;

GotoXY(1,24); TextColor(14); Writeln('Работа программы завершена ...');

Readln;

TextBackGround(0);

TextColor(15);

ClrScr; Key:=true; end;

end;

Until Key; end.



6. Результаты работы программы

Результат работы программы при образовании кода добавлением остатка

Демонстрация Информационный аполином:

0000011010111110011110110110110 Образующий аполином: 111101 Cложениe апо модулю 2 (F(x)+P(x)):

1101011111001111011011011000000 а

Остаток 010101

Передаваемый полинома: 1101011111001111011011011010101

Произошла ошибка... 1101011111001110011011011010101 Ошибка исправлена 1101011111001111011011011010101

Исходный полинома:

0000011010111110011110110110110

Нажмите любую клавишу

Результат работы при аобразовании кода умножением

Демонстрация Информационный полином:

0000001010110000011111010001011

Образующий полином: 111101

Результат умножения: 0110000011111010000100100101111 Произошла ошибка...

0110000011111010000100100101101 Ошибка исправлена! 0110000011111010000100100101111

Нажмите любую клавишу...



Выводы

Данная программа кодирует сообщения используя циклический код.

При этом она имитирует работу канала для передачи информации.

При возникновении исключительных ситуаций, когда информационное слово по каким-либо причинам раскодировать не удаётся, программа повторяет запрос на пересылку данных, как это делается в реальных ситуациях подобного рода. Кроме этого, программа случайным образом, "при прохождении информационного слова через канал" допускает в слове однократную ошибку, затем исправляет ее, декодирует информационное слово и передаёт результат пользователю.



Литература

1. “Кодирование информации (двоичные коды)”.Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. Харьков,издательское объединение “Вища школа”,1978. 252 с.

“ Программирование в среде Turbo Pascal “ . Марченко А.И., Марченко

2. Л.А. Москва,“Бином Универсал”.Киев,”Юниор”,1997.495 с.

Размещено на Allbest.ru

...