Курсовая работа по «Теории информации и кодирования»

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

1. код  четности, который образуется путем  добавления к передаваемой комбинации, состоящей из k информационных символов, одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемой комбинации было четным;

2. код  с постоянным весом, который  содержит постоянное число единиц и нулей;

3. корреляционный  код (код с удвоением), при построении  которого 1 преобразуется в 10, а 0 – в 01;

4. инверсный код, получаемый при  добавлении к исходной комбинации такой же комбинации по длине: если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную комбинацию, если нечетное – то добавляемая комбинация является инверсной относительно исходной;

5. код  Грея, для построения которого  используются следующие правила:

где A_nA_n–1…A₀ – исходная двоичная комбинация, а a_na_n–1…a₀ – соответствующий ей код Грея.

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

A(X) = 1×x⁵ + 0×x⁴ + 1×x³ + 1×x² + 0×x¹ + 1 = x⁵ + x³ + x² + 1.

Циклические коды относятся к систематическим (n, k)-кодам, в которых контрольные r и информационные k разряды расположены на строго определенных местах: n = k + r. При выполнении действий над циклическими кодами в многочленной форме операции умножения и вычитания выполняются как сложение по модулю 2.

Для получения  циклического кода заданный многочлен h(х) сначала умножается на одночлен х^n–k, затем делится на образующий многочлен g(х). В результате получаем:

.

После этого  к произведению h(х)х^n–k добавляется остаток R(x):

F(x) = Q(x) · g(x) = х^n–kh(x) + R(X).

При декодировании, принятую кодовую комбинацию необходимо разделить на g(x). Наличие остатка указывает на ошибку. Образующий полином g(х) является сомножителем при разложении двучлена хⁿ+1. Сомножителями разложения двучлена являются неприводимые полиномы из таблицы 2.

Образующий  полином выбирают следующим образом. По заданной кодовой комбинации k определяют число контрольных символов из соотношения r = log₂(n + 1)  или по эмпирической формуле

r = [log₂{(k + 1) + [log₂(k + 1)]}].

Соотношение значений n, k, r показано в таблице 1.

                                                                                                               Таблица 1

Соотношение между n, k, r

n	3	5	6	7	9…15	17…31	33…63	65…127
k	1	2	3	4	5…11	12…26	27…57	28…120
r	2	3	3	3	4	5	6	7

 

Затем из таблицы 2 выбирают самый короткий неприводимый полином со степенью, равной числу  контрольных символов.

Например,  пусть требуется закодировать комбинацию вида 1101, что соответствует h(х) = х³ + х² + 1.

1. Определяем  число контрольных символов: r = 3.

2. Выбираем  образующий полином: g(х) = х³ + х + 1, т.е. 1011.

3. Умножаем h(х) на х^r:

h(x)x^r = (x³ + x² + 1)x³ = x⁶ + x⁵ + x³ ,

 что соответствует 11010000.

4. Разделим полученное произведение  на образующий полином g(х):

5. Остаток  суммируем с h(х)х^r:

F(x) = (x³ + x² + 1)(x³ + x + 1) = (x³ + x² + 1)x³ + 1, т. е. 1101001.

Полученная кодовая комбинация F(x) циклического кода содержит исходную комбинацию h(х) = 1101 и контрольные символы R(х) = 001. Очевидно, что закодированное сообщение делится на образующий полином без остатка.

Для обнаружения  и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) будет равен 0, то комбинация принята без ошибок. Наличие ненулевого остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей транспонированной проверочной матрицы , который и укажет на местоположение. Проверочная матрица имеет вид:

,

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

.

Тогда, если вместо 1101001 получена кодовая комбинация 1100001, то остаток от деления 1100001 на 1011 будет равен 011. Остаток совпадает  с четвертой строкой матрицы  :

.

Это означает, что ошибка содержится в 4-м разряде, исправив который получаем правильную комбинацию 1101001.

 

 

3.3 Программная реализация и алгоритмы.

 

3.3.1 Запуск программы, входные и выходные данные.

 

Для запуска  программы необходимо кликнуть на файл названием tik_lab3.exe, после этого откроется консольное окно с решением задачи.

Для изменения  входных данных необходимо изменить код программы в файле lab3.cpp/

 

3.3.2 Алгоритмы и функции.

 

 

Программа состоит из нескольких функций, которые вызываются в главной функции main(). Далее представлены эти функции:

• Get_cicl_code- модуль циклического кодирования.
• Get_cod_ves-модуль построения кода с постоянным весом
• Get_code_chetn-модуль кода проверки на четность.
• Get_code_udv- модуль построения кода с удвоением.
• Get_code_invers- модуль построения инверсного кода.
• Get_code_grei- модуль построения кодов Грэя.
• Get_cicl_mistake- получение номера разряда с ошибкой.

 

 

• Алгоритм получения циклического кодирования.

 

void get_cicl_code(char *comb, char *poly, int r, char *code) {

задаем переменные a=0,b=0,c=2;

strcpy(code,comb);

припишем к комбинации нужное количество нулей в соответствии с r

for (int i=0;i<r;i++) {

code[strlen(code)+1]='\0';

code[strlen(code)]='0';

 

}

 

проведем деление по модулю

for (int i=0;i<strlen(code)-strlen(poly)+1;i++) {

if (code[i]=='0') continue;

else {

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (code[i+j]=='1')

code[i+j]='0';

else code[i+j]='1';

}

}

}

}

//припишем

for (int i=0;i<strlen(comb);i++) {

code[i]=comb[i]; 

}

}

 

• Описание модуля получения номера с разрядом ошибки.

 

int get_cicl_mistake(char *code, char *poly) {

задаем массивы temp[MAXL],ostatok[MAXL],ostatok2[MAXL];

strcpy(temp,code);

 

//проведем деление по  модулю

for (int i=0;i<strlen(temp)-strlen(poly)+1;i++) {

if (temp[i]=='0') continue;

else {

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (temp[i+j]=='1')

temp[i+j]='0';

else temp[i+j]='1';

}

}

}

}

 

//перепишем остаток

for (int i=0;i<strlen(poly)-1;i++)

ostatok[i]=temp[strlen(temp)-strlen(poly)+1+i];

ostatok[strlen(poly)-1]='\0';

//

temp[0]='1';

for (int i=0;i<strlen(code)-1;i++) temp[i+1]='0';

temp[strlen(code)]='\0';

 

int c=-1;

//проведем деление по  модулю

for (int i=0;i<strlen(temp)-strlen(poly)+1;i++) {

 

if (temp[i]=='1'){

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (temp[i+j]=='1')

temp[i+j]='0';

else temp[i+j]='1';

}

}

}

for (int j=0;j<strlen(ostatok);j++) ostatok2[j]=temp[1+i+j];//берём остаток 

ostatok2[strlen(ostatok)]='\0';

if (strcmp(ostatok,ostatok2)==0) {c=i;break;}//если  он равен полученному прежде, то выходим

}

 

if (c!=-1)

return strlen(temp)-strlen(poly)-c+1;//получаем  номер разряда с ошибкой

else return -1;

}

 

 

 

 

 

• Описание модуля построения кода с постоянным весом.

 

 

void get_code_ves(char *comb,char *code,int cz, int co) {

strcpy(code,comb);

задаем количество 0 и 1 в  коде

for (int i=0;i<strlen(code);i++) {

if (текущий символ в коде=='0') клличество 0+1; else количество 1+1;

}

for (int i=0;i<cz-ccz;i++) {

приписываем необходимое  колличество 0 в соответствии с заданным весом

}

for (int i=0;i<co-cco;i++) {

приписываем необходимое  колличество 1 в соответствии с заданным весом }

}

• Описание модуля кода с проверкой на четность.

 

 

void get_code_chetn(char *comb,char *code) {

strcpy(code,comb);

задаем количество 0 и 1 =0

for (int i=0;i<strlen(code);i++) {

if (текущий символ кода=='0') количество 0++; else количество 1++;

}

 

if (остаток от деления на 2 колличества едениц==1) {

приписываем 1

} else {

приписываем 0

}

}

 

• Описание модуля кода с удвоением.

 

 

void get_code_udv(char *comb,char *code) {

strcpy(code,comb);

задаем количество 0 и количество 1=0

for (int i=0;i<strlen(comb);i++) {

if (текуший символ=='0') {

в конце приписываем 01

} else {

В конце пишем 10

}

}

Условие конца строки

}

 

 

 

 

 

 

• Описание модуля с инверсным  кодом.

 

 

void get_code_invers(char *comb,char *code) {

strcpy(code,comb);

задаем количество 0 и количество 1=0

for (int i=0;i<strlen(code);i++) {

if (текущий символ=='0') количество 0++; else количество 1++;

}

 

if (колличество 1 четное) {

for (int i=0;i<strlen(comb);i++)

повторяем код; }

else {

for (int i=0;i<strlen(comb);i++)

if (текущий символ=='0') в конце запишем ='1'; else ='0';

}

 

Признак конца стрки;

}

 

• Описание модуля с кодом Грэя.

 

//Код грея

void get_code_grei(char *comb,char *code) {

strcpy(code,comb);

задаем количество 0 и 1=0

for (int i=1;i<strlen(comb);i++) {

if (предыдущий символ'1') {

if (текущий символ =='0') запишем текущим ='1'; else code[i]='0';

}

}

 

}

 

 

 

 

• Описание главного модуля main().

 

int main(){

задаем исходную комбинацию

задаем полином в виде двоичного кода

char code[MAXL];

int r=4;

 

вывод на консоль komb

вызов функции get_cicl_code(comb,g,r,code);

вывод на консольcycle code

code[3]='0';

int raz= вызов функции get_cicl_mistake(code,g);

вывод на консольrazr

 

вызов функции get_code_ves(comb,code,15,15);

вывод на консоль code_ves

вызов функции get_code_chetn(comb,code);

вывод на консоль сode_chetn

 

вызов функции get_code_invers(comb,code);

вывод на консоль code_invers

 

вызов функции get_code_udv(comb,code);

вывод на консоль code_udv

 

вызов функции get_code_grei(comb,code);

вывод на консоль code_grei

 

getch();

возвращаем 0;

}

 

3.3.3 Тестирование.

 

Для проверки правильности работы программы использованы входные данные, которые были теоретически вычислены в ходе выполнения лабораторной работы №3.

Входная кодовая комбинация:

1 0 0 1 1 0 1 0 1 0 1 0

 

 

 

 

 

 

Глава 4. Шифрование данных.

 

4.1 Задание.

 

1.  Выполнить шифрование и дешифрирование заданного сообщения с помощью метода симметричного шифрования с ключом (использовать латинский алфавит). Сообщение выдается из таблицы 1.

2.  Выполнить шифрование и дешифрирование по методу RSA.

 

4.2 Теория.

 

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

C = E_k1(M),

M’ = D_k2(C),

где M – открытая информация (открытый текст), C – полученный в результате зашифровывания шифротекст (криптограмма), E – функция зашифровывания, выполняющая криптографические преобразования над исходным текстом, k1 – параметр функции зашифрования, называемый ключом зашифровывания, M’ – информация, полученная в результате расшифровывания, k2 – параметр для расшифровывания информации, D – функция расшифровывания, выполняющая обратные относительно зашифровывания криптографические преобразования над шифротекстом.

Под ключом, согласно ГОСТ 28147-89, понимается конкретное секретное состояние некоторых  параметров алгоритма криптографического преобразования, обеспечивающее выбор  одного преобразования из совокупности всевозможных для данного алгоритма  преобразований, т.е. ключ – это уникальный элемент, с помощью которого можно  варьировать результат работы алгоритма  шифрования.