Загрузка...
Учебная работа. Курсовая работа: Кодирование информации Код Рида-Малера
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
на тему «Кодирование инфы. Код Рида-Малера «
по курсу «Кодирование и защита инфы»
2003
Содержание
Введение
1 Лишниие коды
2 метод кодировки Рида-Малера
3 Тестовый пример
Вывод
Библиографический перечень
приложение: Текст программки
Введение
Целью истинной работы является закрепление познаний, получаемых в процессе исследования дисциплины, приобретение нужных практических способностей внедрения способов кодировки инфы. В данной курсовой работе рассматривается кодирование инфы способом Рида-Малера. Код Рида-Малера относится к лишним кодам. Заданием на данную работу было создать метод и программку кодировки и декодирования данных кодом Рида-Малера (16,11).
1. Лишниие коды
Лишниие коды – одно из более действенных средств обеспечения высочайшей достоверности передаваемых и принимаемых сообщений.
Лишниие коды могут применяться с целью или лишь обнаружения вероятных ошибок, или исправления найденных ошибок. Во всех вариантах лучше достигнуть наибольшей корректирующей возможности. Но зависимо от определенного построения кода его способность к исправлению тех либо других ошибок может изменяться в широких границах.
При неких значениях n и kможет быть найдено такое удачное построение кода, при котором веса всех разрешенных ненулевых композиций не достаточно различаются друг от друга и от половины очень вероятного веса. При остальных значениях n и kможет оказаться, что для некой малой части кодовых композиций из их общего числа расстояние оказывается значительно наименьшим, чем для большинства остальных. Потому при рассмотрении черт кодов можно найти, что близкие по избыточности и числу разрядов коды резко различаются друг от друга по собственной корректирующей возможности.
В кодах с одной проверкой на четность содержится всего один проверочный знак. Этот знак выбирается таковым, чтоб его сумма по модулю два со всеми информационными знаками равнялась нулю. Благодаря такому способу выбора проверочного знака кодовая композиция содержит четное число единиц. И как следует признаком преломления кодовой композиции является нечетность единиц в принятой композиции. Данный код дозволяет лишь обнаруживать однократные ошибки и все ошибки нечетной кратности.
В кодах с обычным повторением положе способ повторения начальной кодовой композиции. На приемной стороне композиция складывается с начальной и при нулевой сумме композиция принимается. Этот код дозволяет обнаруживать ошибки, кроме ошибок в парных элементах.
Корелляционный код. Умножаются знаки, при всем этом если в разряде информационной части стоит 0, то он заменяется на 01, а 1 – на 10. Сигналом ошибки является возникновение 00 либо 11.
В инверсном коде употребляется повторение начальной композиции последующим образом: если композиция содержит нечетное число единиц, то заместо 1 ставится 0, а всесто 0 – 1. Если четное число единиц, то она умножается без инверсии. На приемной стороне подсчитывается число единиц и, если оно четно, то 2-ая половинка инвертируется и складывается с первой. Если же число единиц четно, то 2-ая складывается с первой и должен получиться 0.
2 Метод кодировки Рида-Малера
Коды Рида-Малера – это блоковые коды, которые строятся последующим образом:
(1) 
(2) 
(3),
n-длина блока
K-число информационных знаков
d-минимальное кодовое расстояние
m-положительное, условное число не меньше 3
s-порядок кода, который постоянно меньше, чем m.
Т.е. зависимо от порядка при одном и том же m можно получить различные коды.
m=4; s=1,2,3; n=24
=16.
Построение кодов Рида-Маллера сводится к последующему.
Сначала строится производящая матрица G, 1-ая строчка которой содержит n единиц. Дальше следует m строк, совокупа которых комфортно разглядывать как (m*n) –матрицу, в качестве столбцов которой выбраны двоичные числа (начиная с нуля). Номера разрядов двоичных чисел комфортно считать сверху вниз. Эти m строк определяют векторы первого порядка d. Дальше идут строчки векторов второго порядка, которые получаются из всех произведений 2-ух строк первого порядка, потом — строчки третьего порядка, являющиеся всеми произведениями 3-х строк первого порядка и т д.
Пример: т=3 s=2 п=2т
=23
=8
Для кодировки определяется общее число знаков в блоке через информационные знаки, суммируя ненулевые позиции соответственного столбика, образующей матрицы. Единицы в столбцах матрицы G демонстрируют, какие конкретно информационные знаки Uk определяют
Пусть пришла последовательность:
Получаем: 11101011
Декодирование осуществляется по мажоритарному принципу либо принципу большинства.
Декодирование осуществляется сначала для всех информационных знаков (не считая 1-го) на базе так именуемых парных компонент. Начинать запись таковых уравнений нужно с векторов наибольшего порядка.
В нашем примере s=2=> первым выписывается Uk
5
.
Для векторов 2-го порядка парными числятся составляющие:
00 ® 0
01 ® 1
На втором уровне сочетаний любой 0 соединяется с каждой 1 попарно. сейчас в проверяемое равенство выписываются все объединенные позиции 1-го и 2-го уровней.
Вычисляем знак Uk6
Для Uk7
:
При декодировании при помощи векторов 1-го порядка мы также буквально пользуемся парными компонентами, но так как тут 1-ый уровень, то мы объединяем просто 0 и 1, стоящую на соответственных позициях, и, во-2-х, при декодировании в приобретенных уравнениях употребляют не начальное, а перевоплощенное уравнение, которое выходит методом сложения по модулю два начального уравнения и векторов 2-го порядка, (поэтому что матрица имеет 2-ой порядок),
Опосля этого снова конвертируют начальное выражение: к приобретенному перевоплощенному выражению прибавляем векторы 1-го порядка, которые содержат единицу в соответственном информационном разряде.
Если в приобретенном выражении получили все 1, то означает Uk
1
=1, а если все 0, то Uk
1
=0.
Если при передаче произошли преломления, то вычисляемый знак по каждой системе проверок выбирается по мажоритарному принципу, в том числе и для знака Uk
1
.
3 Тестовый пример
В качестве тестового примера использовалась композиция 11001010000.
В задании к курсовому проекту обозначено, что n=16, а k=11. Таковым образом получили образующую матрицу, которая имеет последующий вид:
Построение матрицы реализовано программно для данных n и k.
Опосля кодировки начальной композиции 11001010000 по приобретенной образующей матрице получили комбинацию1010111101010000. При всем этом мы суммируем те разряды начальной композиции, на соответственных позициях которых, в рассматриваемом столбце образующей матрицы, стоят единицы. к примеру, возьмем 4-ый столбец. Единицы имеются в разрядах 1,2,3,6. При суммировании этих разрядов получим 0. Другими словами в закодированной композиции в четвертом разряде получили 0:
Декодирование осуществляется по мажоритарному признаку, другими словами при декодировании любой разряд композиции проверяется несколькими уравнениями. Благодаря этому реально избежать ошибок при передаче. Даже если в каком-либо разряде ошибка, она поменяет итог лишь 1-го уравнения. А в других итог остается этот же.
Вывод
В процессе курсовой работы был изучен обычной помехоустойчивый код, а конкретно код Рида-Малера. Данный код обнаруживает ошибки, но не исправляет их. Рассматривался вариант, когда n=16, k=11, потому в матрице находятся лишь вектора первого и второго порядка. Но если покажется необходимость употреблять также вектора третьего порядка, то образующая матрица станет существенно больше, что не прибыльно исходя из убеждений экономии памяти. При всем этом также возрастет длина закодированной композиции, что прирастит время передачи сообщения по каналу связи.
Библиографический перечень
1. Березюк Н.Т. «Кодирование Инфы» — 1978.
2. Конспект лекций по дисциплине «Кодирование и защита инфы».
Приложение
Текст программки
//—————————————————————————
#include <vcl.h>
#pragma hdrstop
#include «Unit1.h»
//—————————————————————————
#pragma package(smart_init)
#pragma resource «*.dfm»
TForm1 *Form1;
const N=16;
const K=11;
char *s;
int f,l[11],l1[16];
//—————————————————————————
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{int i,j;
for (i=0;i<N;i++)
{ StringGrid1->Cells[i][0]=1; }
for (i=0;i<N;i++)
{ StringGrid1->Cells[i][1]=0;
i++; StringGrid1->Cells[i][1]=1; }
for (i=0;i<N;i++)
{ StringGrid1->Cells[i][2]=0;
i++; StringGrid1->Cells[i][2]=0;
i++; StringGrid1->Cells[i][2]=1;
i++; StringGrid1->Cells[i][2]=1; }
for (i=0;i<N;i++)
{ if (i<N/2)
{ StringGrid1->Cells[i][4]=0; }
else
{ StringGrid1->Cells[i][4]=1; }
}
for (i=0;i<N;i++)
{ if (7<i&&i<12||4>i&&i<8)
{ StringGrid1->Cells[i][3]=0; }
else { StringGrid1->Cells[i][3]=1; }
}
int b;
int k1,k2,a=5;
j=1; b=1;
for (j;j<4;j++)
{ for(i=0;i<N;i++)
{ k1=StringGrid1->Cells[i][b].ToInt();
j++; k2=StringGrid1->Cells[i][j].ToInt(); j—;
if (k1==1&&k2==1)
{ StringGrid1->Cells[i][a]=1; }
else
{ StringGrid1->Cells[i][a]=0; }
}
a++; }
b=2; j=2;
for (j;j<4;j++)
{ for(i=0;i<N;i++)
{ k1=StringGrid1->Cells[i][b].ToInt(); j++;
k2=StringGrid1->Cells[i][j].ToInt(); j—;
if (k1==1&&k2==1)
{ StringGrid1->Cells[i][a]=1; }
else
{ StringGrid1->Cells[i][a]=0; }
}
a++;
}
b=3; j=3;
for (j;j<4;j++)
{ for(i=0;i<N;i++)
{ k1=StringGrid1->Cells[i][b].ToInt(); j++;
k2=StringGrid1->Cells[i][j].ToInt(); j—;
if (k1==1&&k2==1)
{ StringGrid1->Cells[i][a]=1; }
else
{ StringGrid1->Cells[i][a]=0; }
}
}
s=» «; Edit1->Text=s;
Edit1->MaxLength=12;
Memo1->Text=s;
Memo1->Lines->Add(«U1=Uk1»);
Memo1->Lines->Add(«U2=Uk1+Uk2»);
Memo1->Lines->Add(«U3=Uk1+Uk3»);
Memo1->Lines->Add(«U4=Uk1+Uk2+Uk3+Uk6»);
Memo1->Lines->Add(«U5=Uk1+Uk4»);
Memo1->Lines->Add(«U6=Uk1+Uk2+Uk4+Uk7»);
Memo1->Lines->Add(«U7=Uk1+Uk3+Uk4+Uk9»);
Memo1->Lines->Add(«U8=Uk1+Uk2+Uk3+Uk4+Uk6+Uk7+Uk9»);
Memo1->Lines->Add(«U9=Uk1+Uk5»);
Memo1->Lines->Add(«U10=Uk1+Uk2+Uk5+Uk8»);
Memo1->Lines->Add(«U11=Uk1+Uk3+Uk5+Uk10»);
Memo1->Lines->Add(«U12=Uk1+Uk2+Uk3+Uk5+Uk6+Uk8+Uk10»);
Memo1->Lines->Add(«U13=Uk1+Uk4+Uk5+Uk11»);
Memo1->Lines->Add(«U14=Uk1+Uk2+Uk4+Uk5+Uk7+Uk8+Uk11»);
Memo1->Lines->Add(«U15=Uk1+Uk3+Uk4+Uk5+Uk9+Uk10+Uk11»);
Memo1->Lines->Add(«U16=Uk1+Uk2+Uk3+Uk4+Uk5+Uk6+Uk7+Uk8+Uk9+Uk10+Uk11»);}
//—————————————————————————
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{s=Edit1->Text.c_str();
for(int i=1;i<K+1;i++)
{ l[i-1]=StrToInt(s[i]); }
for (int i=0;i<N;i++)
{ f=0;
for (int j=0;j<K;j++)
{ if (StringGrid1->Cells[i][j]==1)
{ f=l[j]+f; if (f==2) f=0;
}
l1[i]=f;
}
}
for(int i=0;i<N;i++)
{ StringGrid2->Cells[i][0]=l1[i];
}
}
//—————————————————————————
void __fastcall TForm1::Button2Click(TObject *Sender)
{ int ed, nul,i,j,perem[4];
int l2[16]; int edin1=0,edin2=0,edin3=0,edin4=0,edin5=0,edin6=0;
ed=0; nul=0;
for(int i=0;i<N;i++)
{ l1[i]=StringGrid2->Cells[i][0].ToInt(); }
for(i=0;i<N;i++)
{ l2[i]=l1[i]; }
perem[0]=l1[0]+l1[4]+l1[8]+l1[12]; perem[1]=l1[1]+l1[5]+l1[9]+l1[13];
perem[2]=l1[2]+l1[6]+l1[10]+l1[14];perem[3]=l1[3]+l1[7]+l1[11]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[10][0]=1; edin1=10; }
else
{ StringGrid3->Cells[10][0]=0; }
//——————————
ed=0; nul=0;
perem[0]=l1[0]+l1[2]+l1[8]+l1[10]; perem[1]=l1[1]+l1[3]+l1[9]+l1[11];
perem[2]=l1[4]+l1[6]+l1[12]+l1[14]; perem[3]=l1[5]+l1[7]+l1[13]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[9][0]=1; edin2=9; }
else
{ StringGrid3->Cells[9][0]=0; }
//—————————-
ed=0; nul=0;
perem[0]=l1[0]+l1[2]+l1[4]+l1[6]; perem[1]=l1[1]+l1[3]+l1[5]+l1[7];
perem[2]=l1[8]+l1[10]+l1[12]+l1[14]; perem[3]=l1[9]+l1[11]+l1[13]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[8][0]=1; edin3=8; }
else
{ StringGrid3->Cells[8][0]=0; }
//—————————-
ed=0; nul=0;
perem[0]=l1[0]+l1[1]+l1[8]+l1[9]; perem[1]=l1[2]+l1[3]+l1[10]+l1[11];
perem[2]=l1[4]+l1[5]+l1[12]+l1[13]; perem[3]=l1[6]+l1[7]+l1[14]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[7][0]=1; edin4=7; }
else
{ StringGrid3->Cells[7][0]=0; }
//—————————
ed=0; nul=0;
perem[0]=l1[0]+l1[1]+l1[4]+l1[5]; perem[1]=l1[2]+l1[3]+l1[6]+l1[7];
perem[2]=l1[8]+l1[9]+l1[12]+l1[13]; perem[3]=l1[10]+l1[11]+l1[14]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[6][0]=1; edin5=6; }
else
{ StringGrid3->Cells[6][0]=0; }
//—————————-
ed=0; nul=0;
perem[0]=l1[0]+l1[1]+l1[2]+l1[3]; perem[1]=l1[4]+l1[5]+l1[6]+l1[7];
perem[2]=l1[8]+l1[9]+l1[10]+l1[11]; perem[3]=l1[12]+l1[13]+l1[14]+l1[15];
for (i=0;i<4;i++)
{ if (perem[i]==1||perem[i]==3)
{ perem[i]=1; ++ed; }
else
{ perem[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[5][0]=1; edin6=5; }
else
{ StringGrid3->Cells[5][0]=0; }
//ПРЕОБРАЗОВАНHOЕСООБЩЕНИЯ
if (edin1!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][10].ToInt(); }
if (edin2!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][9].ToInt(); }
if (edin3!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][8].ToInt(); }
if (edin4!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][7].ToInt(); }
if (edin5!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][6].ToInt(); }
if (edin6!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][5].ToInt(); }
for(i=0;i<N;i++)
{ if (l1[i]==1||l1[i]==3||l1[i]==5||l1[i]==7)
{ l1[i]=1; }
else
{ l1[i]=0; }
}
//————————————
int edin7=0,edin8=0,edin9=0,edin10=0;
ed=0;nul=0;
int perem1[8];
perem1[0]=l1[0]+l1[8]; perem1[1]=l1[1]+l1[9];
perem1[2]=l1[2]+l1[10]; perem1[3]=l1[3]+l1[11];
perem1[4]=l1[4]+l1[12]; perem1[5]=l1[5]+l1[13];
perem1[6]=l1[6]+l1[14]; perem1[7]=l1[7]+l1[15];
for (i=0;i<4;i++)
{ if (perem1[i]==1||perem1[i]==3||perem1[i]==5||perem1[i]==7)
{ perem1[i]=1; ++ed; }
else
{ perem1[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[4][0]=1; edin7=6; }
else
{ StringGrid3->Cells[4][0]=0; }
//——————————
ed=0; nul=0;
perem1[0]=l1[0]+l1[4]; perem1[1]=l1[1]+l1[5];
perem1[2]=l1[2]+l1[6]; perem1[3]=l1[3]+l1[7];
perem1[4]=l1[8]+l1[12]; perem1[5]=l1[9]+l1[13];
perem1[6]=l1[10]+l1[14]; perem1[7]=l1[11]+l1[15];
for (i=0;i<4;i++)
{ if (perem1[i]==1||perem1[i]==3||perem1[i]==5||perem1[i]==7)
{ perem1[i]=1; ++ed; }
else
{ perem1[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[3][0]=1; edin8=7; }
else
{ StringGrid3->Cells[3][0]=0; }
//———————————-
ed=0; nul=0;
perem1[0]=l1[0]+l1[2]; perem1[1]=l1[1]+l1[3];
perem1[2]=l1[4]+l1[6]; perem1[3]=l1[5]+l1[7];
perem1[4]=l1[8]+l1[10]; perem1[5]=l1[9]+l1[11];
perem1[6]=l1[12]+l1[14]; perem1[7]=l1[13]+l1[15];
for (i=0;i<4;i++)
{ if (perem1[i]==1||perem1[i]==3||perem1[i]==5||perem1[i]==7)
{ perem1[i]=1; ++ed; }
else
{ perem1[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[2][0]=1; edin9=8; }
else
{ StringGrid3->Cells[2][0]=0; }
//—————————-
ed=0; nul=0;
perem1[0]=l1[0]+l1[1]; perem1[1]=l1[2]+l1[3];
perem1[2]=l1[4]+l1[5]; perem1[3]=l1[6]+l1[7];
perem1[4]=l1[8]+l1[9]; perem1[5]=l1[10]+l1[11];
perem1[6]=l1[12]+l1[13]; perem1[7]=l1[14]+l1[15];
for (i=0;i<4;i++)
{ if (perem1[i]==1||perem1[i]==3||perem1[i]==5||perem1[i]==7)
{ perem1[i]=1; ++ed; }
else
{ perem1[i]=0; ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[1][0]=1; edin10=9; }
else
{ StringGrid3->Cells[1][0]=0; }
//2-e преобразование
int l3[11];
if (edin7!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][4].ToInt(); }
if (edin8!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][3].ToInt(); }
if (edin9!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][2].ToInt(); }
if (edin10!=0)
for (i=0;i<N;i++)
{ l1[i]=l1[i]+StringGrid1->Cells[i][1].ToInt(); }
for(i=0;i<N;i++)
{ if (l1[i]==1||l1[i]==3||l1[i]==5)
{ l1[i]=1; }
else
{ l1[i]=0; }
}
//——————————-
int perem2=0;
for(i=0;i<N;i++)
{ if (l1[i]==1)
{ ++ed; }
else
{ ++nul; }
}
if (nul<ed)
{ StringGrid3->Cells[0][0]=1; }
else
{ StringGrid3->Cells[0][0]=0; }
}
//—————————————————————————
]]>