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

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

Министерство образования Российской Федерации

Московский государственный институт электроники и математики

Факультет автоматики и вычислительной техники

Кафедра

Электронно-вычислительная аппаратура

Курсовая работа

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

Код Хэмминга с и

Выполнил:

студент 4^го курса группы С-75

Дубровин Н. А.

Проверила:

Гоманилова Н.Б.

Оглавление

• Введение
• Алгоритм кодирования
• Алгоритм декодирования
• Код Хэмминга
• Код Хэмминга
• Установка и использование программы
• Требования к программному обеспечению
• Порядок установки
• Использование программы
• Ограничения
• Пример работы
• Приложение. Исходный код программы


Введение

Код Хэмминга - простейший линейный код, способный обнаружить ошибки кратности и исправить ошибки кратности , где - минимальное кодовое расстояние. В работе использовался код Хэмминга с и .

Целью данной работы является практическое освоение кода Хэмминга с минимальным кодовым расстоянием 3 и 4. Для этого требуется разработать программу, реализующую код Хэмминга; способную закодировать входное слово, декодировать его, определить наличие ошибки при передаче и, если возможно, исправить ее.

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



Алгоритм кодирования

хэмминг кодовый слово программа

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

Информационные разряды - разряды, содержащие входное слово в двоичном виде. Для определения их количества нужно посчитать количество разрядов входного слова в двоичном виде.

Контрольные разряды - избыточные разряды, необходимые для обнаружения и корректирования ошибок при передаче. Такие разряды рассчитываются определенным образом в зависимости от используемого кода. Для кода Хэмминга количество контрольных разрядов рассчитывается исходя из неравенства:

,

Где m - число информационных разрядов, k - число контрольных разрядов.

Длина кодового слова - сумма количества информационных и контрольных разрядов. Для кода Хэмминга с минимальным кодовым расстоянием 4 длина кодового слова увеличивается за счет дополнительного контрольного разряда.

Следующий шаг - расчет значений контрольных разрядов. Алгоритм расчета таков:

· Расчет 1го контрольного разряда (1й разряд слова):

o пропустить 0 разрядов;

o добавить в расчет дополнения до четности 1 разряд;

o пропустить 1 разряд;

o добавить в расчет дополнения до четности 1 разряд;

o пропустить 1 разряд;

o и так далее.

· Расчет 2го контрольного разряда (2й разряд слова):

o пропустить 1 разрядов;

o добавить в расчет дополнения до четности 2 разряда;

o пропустить 2 разряда;

o добавить в расчет дополнения до четности 2 разряда;

o пропустить 2 разряд;

o и так далее.

· Расчет 3го контрольного разряда (4й разряд слова):

o пропустить 3 разрядов;

o добавить в расчет дополнения до четности 4 разряда;

o пропустить 4 разряда;

o добавить в расчет дополнения до четности 4 разряда;

o пропустить 4 разряд;

o и так далее.

Таким образом, контрольный разряд рассчитывается по формуле:

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



Алгоритм декодирования

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

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

В случае несовпадения пришедшего и рассчитанного контрольного разряда в регистр ошибок записывается 1, в противном случае - 0.

После расчета всех контрольных разрядов необходимо интерпретировать значение регистра ошибок. Для кодов Хэмминга с минимальным кодовым расстоянием 3 существует 2 возможных варианта, в то время как для вариантов - 4.

Код Хэмминга

1. Ошибок нет.

Доп. КР	k - 1	…	6	5	4	3	2	1	0
0	0	…	0	0	0	0	0	0	0

В дополнительном контрольном разряде - 0.

В основных контрольных разрядах - 0.

2. Одиночная ошибка.

Доп. КР	k - 1	…	6	5	4	3	2	1	0
1	0	…	0	0	1	1	0	1	0

В дополнительном контрольном разряде - 1.

В основных контрольных разрядах - не 0 (номер ошибочного разряда в двоичном виде).

3. Двоичная ошибка (не корректируется).

Доп. КР	k - 1	…	6	5	4	3	2	1	0
0	1	…	0	0	1	1	1	0	0

В дополнительном контрольном разряде - 0.

В основных контрольных разрядах - не 0.

4. Ошибка в дополнительном контрольном разряде.

Доп. КР	k - 1	…	6	5	4	3	2	1	0
1	0	…	0	0	0	0	0	0	0

В дополнительном контрольном разряде - 1.

В основных контрольных разрядах - 0.

Код Хэмминга

1. Ошибок нет.

k - 1	…	6	5	4	3	2	1	0
0	…	0	0	0	0	0	0	0

В основных контрольных разрядах - 0.

2. Одиночная ошибка.

k - 1	…	6	5	4	3	2	1	0
0	…	0	1	0	1	1	0	1

В основных контрольных разрядах - не 0 (номер ошибочного разряда в двоичном виде).



Установка и использование программы. Требования к программному обеспечению

Для установки программы требуется:

· ОС GNU/Linux или BSD;

· Компилятор g++ языка Си++;

· Библиотека STL языка Си++.

Порядок установки

1. Распаковать архив hamming.tar.gz. Для этого в консоли необходимо выполнить команду:

nikitad@sotona:~$ tar -zxvf ./hamming.tar.gz

Архив будет распакован в текущий каталог.

2. Перейти в директорию, содержащую исходные тексты программы:

nikitad@sotona~$ cd hamming/

3. Выполнить конфигурирование компилятора:

nikitad@sotona~/hamming$ ./configure

4. Скомпилировать и установить от имени привилегированного пользователя:

nikitad@sotona~/hamming$ make

nikitad@sotona~/hamming$ sudo make install

Перед выполнением последней команды будет запрошен пароль пользователя root.

Использование программы

Для начала работы программы нужно набрать в командной строке:

nikitad@sotona~$ hamming

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

hamming [-i|--interactive] [input_num]

hamming [-d|--dmin=3] [-e|--error=err_bits] [input_num]

В данном случае input_num - десятичное число, которое требуется закодировать. Если его не указать в качестве аргумента программы, то оно будет запрошено после запуска.

При вызове программы можно указать следующие параметры:

· -i, --interactive - запуск программы в интерактивном режиме. В этом режиме программа будет запрашивать требуемые ей параметры по мере необходимости. Любые другие указанные аргументы игнорируются.

· -d, --dmin - указывает минимальное кодовое расстояние, которое будет использоваться при кодировании/декодировании. Если этот параметр не указан, то используется значение 3.

· -e, --error - указывает номера разрядов, которые требуется обратить (искусственно создать ошибку). Разряды нумеруются, начиная с нуля. Для указания нескольких (не более двух при и не более одного при ) разрядов следует разделить их запятой (без пробела). Для отмены создания ошибки нужно ввести два одинаковых номера.

Ограничения

· Длина кодового слова должна быть не более 32 бит, считая дополнительный контрольный разряд.

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

· Программу рекомендуется запускать на экране с разрешением не менее 1024х768, в противном случае нарушается требуемый вид вывода на экран.

Пример работы

nikitad@sotona:~$ hamming --dmin=4 --error=3 4376

hamming

--dmin=4

--error=3

4376

==================================================

Знак = найден на позиции 6

Обработка аргумента --dmin

--dmin = 4

Переменная 'dmin' установлена на 4

=================================================

Знак = найден на позиции 7

Обработка аргумента --error

--error = 3

Переменная 'error_bits' установлена на 3 =====================================================

Входное слово 4376

=================================================

Имеется дополнительный контрольный разряд.

Входное слово: 00000000000000000001000100011000

Информационные разряды: 13

Контрольные разряды (исключая дополнительный): 5

Длина закодированного слова: 19

1: 0 0 1 1 0 1 0 0 Контрольный разряд №0: 1

2: 0 01 00 00 1 Контрольный разряд №1: 0

3: 001 0100 Контрольный разряд №3: 0

4: 1000100 Контрольный разряд №7: 0

5: 01 Контрольный разряд №15: 1

Дополнительный контрольный разряд равен 0

Закодированное слово (dmin=4): 00000000000000101001000101000001

Изменение разряда #3

Закодированное слово с ошибкой: 00000000000000101001000101001001

1: 0 0 1 1 0 1 0 0 Рассчитанный КР 0 = 1 Пришедший КР 0 = 1 Совпадение: 0

2: 0 01 00 00 1 Рассчитанный КР 1 = 0 Пришедший КР 1 = 0 Совпадение: 0

3: 001 0100 Рассчитанный КР 3 = 0 Пришедший КР 3 = 1 Несовпадение: 1

4: 1000100 Рассчитанный КР 7 = 0 Пришедший КР 7 = 0 Совпадение: 0

5: 01 Рассчитанный КР 15 = 1 Пришедший КР 15 = 1 Совпадение: 0

Проверка дополнительного контрольного разряда.

Вычисленный КР: 1 Пришедший контрольный разряд: 0 Несовпадение: 1

Регистр ошибок: 00000000000000000000000000100100

Ошибка в разряде #3

nikitad@sotona:~$



Приложение. Исходный код программы

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

#include <list>

#include <bitset>

#include <cmath>

using namespace std;

int decodeErrorRegister(bitset<32>, int);

bool strtoint (string, int*);

bool isParityBit (int, int);

bitset<32> encode (bitset<32>, int, int, int, int);

bitset<32> decode (bitset<32>, int, int, int, int);

int main(int argc, char** argv[])

{

// Переменные-счетчики

int i = 0, j = 0, l = 0;

// Dmin

int dmin = 3;

// Используется при разборе аргументов программы для временного хранения

// номера ошибочного разряда

int TempErrorBit = -1;

// Входное число

int input = -1;

// Делимое, используется при подсчете числа контрольных разрядов

int Dividual = -1;

// Остаток от деления, используется при подсчете числа контрольных разрядов

int Remainder = -1;

// Количество информационных разрядов, длина закодированного слова,

// количество контрольных разрядов

int m = 0, n = 0, k = 0;

// Результат сложения разрядов регистра ошибок, исключая дополнительный

// контрольный разряд

int ErrorRegisterSum = 0;

// Интерактивный режим

bool interactive = false;

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

// программы

size_t fnd, oldfnd;

// Длина некоторой строки, используется для разбора аргументов

// программы

size_t len;

// Переменная для хранения имени аргумента, используется для разбора аргументов

// аргументов программы

string ArgTemp = "";

// Переменная для хранения значения аргумента, используется для разбора аргументов

// аргументов программы

string ValTemp = "";

// Буфер обработки, используется для разбора аргументов программы

string ParseBuffer = "";

// Используется для хранения введенных номеров ошибочных разрядов в

// интерактивном режиме

string ErrorBitString = "";

// Список ошибочных разрядов

list <int> error_bits;

// Итератор для списка ошибочных разрядов

list <int>::iterator it;

// Закодированное слово

bitset<32> encoded_word;

// Регистр ошибок

bitset<32> error_register;

// Аргументы порграммы

vector <string> Arguments(argc);

// Заполнение вектора аргументов

for (i = 0; i < argc; i++) {

Arguments[i].assign ((const char*)argv[i], strlen((const char *)argv[i]));;

cout << Arguments[i] << endl;

}

// Обработка аргументов

for (i = 0; i < argc; i++) {

// Если указан интерактивный режим работы программы.

if ((Arguments[i] == "--interactive") || (Arguments[i] == "-i")) {

interactive = true;

cout << "Программа запущена в интерактивном режиме, аргументы игнорируются." << endl;

}

// Поиск знака =

if ((fnd = Arguments[i].find("=")) != string::npos) {

cout << "Знак = найден на позиции " << fnd << endl;

len = Arguments[i].length();

ArgTemp = Arguments[i].substr(0,(int)fnd);

ValTemp = Arguments[i].substr((int)fnd + 1,len - (int)fnd);

cout << "Обработка аргумента " << ArgTemp << endl;

// Если указан dmin в качетсве аргумента программы

if ((ArgTemp == "--dmin") || (ArgTemp == "-d")) {

cout << ArgTemp << " = " << ValTemp << endl;

strtoint (ValTemp, &dmin);

cout << "Переменная 'dmin' установлена на " << dmin << endl;

}

// Если указан(ы) номер(а) ошибочных разрядов в аргументе программы

if ((ArgTemp == "--error") || (ArgTemp == "-e")) {

cout << ArgTemp << " = " << ValTemp << endl;

ParseBuffer = "";

for (j = 0; j <= ValTemp.length(); j++) {

ParseBuffer += ValTemp.substr(j,1);

if ((ValTemp.compare((size_t)j, 1, ",") == 0) || (j == ValTemp.length())) {

strtoint (ParseBuffer, &TempErrorBit);

// Добавление номера разряда в список ошибочных

error_bits.push_back (TempErrorBit);

ParseBuffer = "";

continue;

}

}

list<int>::iterator it;

cout << "Переменная 'error_bits' установлена на ";

for (it = error_bits.begin(); it != error_bits.end(); it++) {

cout << " " << *it;

}

cout << endl;

}

}

if (strtoint (Arguments[i], &input) == true) {

cout << "Входное слово " << input << endl;

}

cout << "=================================" << endl;

}

// В интерактивном режиме параметры кодирования запрашиваются в процессе

// работы прогаммы

if (interactive == true) {

cout << "Введите dmin: " << endl;

cin >> dmin;

}

if ((input == -1) || (interactive == true)) {

cout << "Введите десятичное число: " << endl;

cin >> input;

}

// Инициализация набора битов входным десятичным числом

bitset<32> input_seq(input);

// Подсчет количества информационных разрядов

Dividual = input;

while (Dividual > 0) {

Remainder = Dividual % 2;

Dividual = Dividual / 2;

m++;

}

// Подсчет количества контрольных разрядов (2^k = m + k + 1).

while (pow(2.0,k) < m + k + 1) {

k++;

}

// Длина закодированного слова

n = m + k;

// Если dmin = 4, то увеличить длину закодированного слова на единицу

if (dmin == 4) {

cout << "Имеется дополнительный контрольный разряд." << endl;

n += 1;

}

cout << "Входное слово:\t\t\t\t" << input_seq << endl;

cout << "Информационные разряды:\t\t\t" << m << endl;

cout << "Контрольные разряды (исключая дополнительный):\t" << k << endl;

cout << "Длина закодированного слова:\t\t\t" << n << endl;

// Вызов процедуры кодирования

encoded_word = encode (input, dmin, m, n, k);

// Ввод номеров ошибочных разрядов для интерактивного режима или случая,

// когда список номеров ошибочных разрядов пуст

if ((error_bits.empty() == true) || (interactive == true)) {

cout << "Введите номера ошибочных разрядов через запятую (для отмены ошибки введите номер разряда 2 раза): " << endl;

cin >> ErrorBitString;

ParseBuffer = "";

for (j = 0; j <= ErrorBitString.length(); j++) {

ParseBuffer += ErrorBitString.substr(j,1);

if ((ErrorBitString.compare((size_t)j, 1, ",") == 0) || (j == ErrorBitString.length())) {

strtoint (ParseBuffer, &TempErrorBit);

error_bits.push_back (TempErrorBit);

ParseBuffer = "";

continue;

}

}

cout << "Переменная 'error_bits' установлена на ";

for (it = error_bits.begin(); it != error_bits.end(); it++) {

cout << " " << *it;

}

cout << endl;

}

// Создание ошибки

for (it = error_bits.begin(); it != error_bits.end(); it++) {

cout << "Изменение разряда #" << *it << endl;

encoded_word.flip(*it);

}

cout << "Закодированное слово с ошибкой:\t" << encoded_word << endl;

// Вызов процедуры декодирования

error_register = decode (encoded_word, dmin, m, n, k);

cout << "Регистр ошибок:\t" << error_register << endl;

// Рассчет суммы разрядов регистра ошибок (исключая дополнительный

// контрольный)

for (i = 0; i < k; i++) {

if (error_register[i] == 1) {

ErrorRegisterSum++;

}

}

// Интерпретация результата декодирования для dmin = 4

if (dmin == 4) {

// Если дополнительный контрольный разряд равен 0

if (error_register[k] == 0) {

// Если сумма остальных разрядов 0 (все нули), то ошибок нет.

if (ErrorRegisterSum == 0) {

cout << "Ошибок нет." << endl;

// В противном случае - некорректируемая двойная ошибка.

} else {

cout << "Двойная ошибка (не корректируется)." << endl;

}

// Если дополнительный контрольный разряд равен 1

} else {

// Если сумма остальных разрядов 0 (все нули), то ошибка в

// дополнительном контрольном разряде

if (ErrorRegisterSum == 0) {

cout << "Ошибка в дополнительном контрольном разряде." << endl;

// В противном случае - одиночная корректируемая ошибка: дешифруем

// регистр ошибок и получаем номер ошибочного разряда в десятичной

// системе счисления

} else {

int decbitnum = decodeErrorRegister(error_register, k);

cout << "Ошибка в разряде #" << decbitnum << endl;

}

}

// Интерпретация результата декодирования для dmin = 3

} else {

// Если сумма разрядов 0 (все нули), то ошибок нет.

if (ErrorRegisterSum == 0) {

cout << "Ошибок нет." << cout;

// В противном случае - одиночная корректируемая ошибка: дешифруем

// регистр ошибок и получаем номер ошибочного разряда в десятичной

// системе счисления

} else {

int decbitnum = decodeErrorRegister(error_register, k);

cout << "Ошибка в разряде #" << decbitnum << endl;

}

}

exit (0);

}

bool strtoint(string Convstr, int* result) {

int i;

istringstream cnvStream(Convstr);

if (cnvStream >> i) {

*(result) = i;

return true;

} else {

return false;

}

}

bitset<32> encode (bitset<32> input_seq, int dmin, int m, int n, int k) {

// Переменные-счетчики

int i = 0, j = 0, l = 0;

// Номер текущего разряда

int CurrentBit = 0;

// Число пропускаемых разрядов

int Skip = 0;

// Дополнительный контрольных разряд не участвует в рассчете

int nact = 0;

// Флаг проверки разрядов

bool check = true;

// Переменная для временного хранения дополнения до четности по

//подмножеству

bool ParityTemp = false;

// Закодированное слово

bitset<32> encoded_word;

// Добавление контрольных разрядов во входное слово

for (i = 0; i <= n; i++) {

if (i == ((int) pow (2.0, l) - 1)) {

l++;

continue;

}

encoded_word.set(i, input_seq[j]);

j++;

}

dmin == 4 ? nact = n - 1 : nact = n;

// Рассчет каждого контрольного разряда (кроме дополнительного)

for (i = 0; i < k; i++) {

cout << i + 1 << ": ";

// Установка флага проверки

check = true;

// Обнуление переменной хранения дополнения до четности

ParityTemp = false;

// Рассчет номера текущего контрольного разряда

CurrentBit = (int) pow (2.0, i) - 1;

// Рассчет числа разрядов, которые нужно пропустить

Skip = (int) pow (2.0, i);

for (j = 0; j <= CurrentBit; j++) {

cout << " ";

}

// Просмотр разрядов начиная с CurrentBit до конца слова с шагом Skip

for (j = CurrentBit; j <= nact; j = j + Skip) {

// Считаем Skip разрядов

for (l = 0; l < Skip; l++) {

// Если текущий разряд - контрольный, то пропуск

if ((isParityBit(j + l, k) == true) || (j + l >= nact)) {

cout << " ";

continue;

}

// Если установлен флаг проверки разрядов, то j + l разряд

// складываем по модулю 2 с временной переменной дополнения

// до четности.

// В противном случае вывод пробела.

if (check == true) {

cout << encoded_word[j + l];

ParityTemp ^= encoded_word[j + l];

//cout << i << "\t" << j << "\t" << l << "\t" << j + l << endl;

} else {

cout << " ";

}

}

// Обращение флага проверки разрядов

check = ! check;

}

// Сохранение временной переменной хранения дополнения до четности

cout << "\t\tКонтрольный разряд №" << (int) pow (2.0, i) - 1 << ": " << ParityTemp;

cout << endl;

encoded_word.set(CurrentBit, ParityTemp);

}

// Сброс временной переменной хранения дополнения до четности

ParityTemp = false;

// Рассчет дополнительного контрольного разряда

if (dmin == 4) {

for (i = 0; i <= nact; i++) {

ParityTemp ^= encoded_word[i];

}

cout << "Дополнительый контрольный разряд равен " << ParityTemp << endl;

encoded_word.set(nact, ParityTemp);

}

cout << "Закодированное слово (dmin=" << dmin << "):\t" << encoded_word << endl;

return encoded_word;

}

bitset<32> decode(bitset<32> damaged_word, int dmin, int m, int n, int k) {

// См. соответствующие переменные процедуры кодирования

bool check = false;

bool ParityTemp = false;

int CurrentBit = -1;

int Skip = -1;

int nact = -1;

int i = 0, j = 0, l = 0;

// Регистр ошибок

bitset<32> error_register(0);

dmin == 4 ? nact = n - 1 : nact = n;

// Рассчет контрольных разрядов заново. Если рассчитаный и пришедший

// контрольные разряды совпали, то в регистр ошибок идет 0, иначе - 1

for (i = 0; i < k; i++) {

cout << i + 1 << ": ";

check = true;

ParityTemp = false;

CurrentBit = (int) pow (2.0, i) - 1;

Skip = (int) pow (2.0, i);

for (j = 0; j <= CurrentBit; j++) {

cout << " ";

}

for (j = CurrentBit; j <= nact; j = j + Skip) {

for (l = 0; l < Skip; l++) {

if ((isParityBit(j + l, k) == true) || (j + l >= nact)) {

cout << " ";

continue;

}

if (check == true) {

cout << damaged_word[j + l];

ParityTemp ^= damaged_word[j + l];

//cout << i << "\t" << j << "\t" << l << "\t" << j + l << endl;

} else {

cout << " ";

}

}

check = ! check;

}

cout << "\t\tРассчитаный КР " << (int) pow (2.0, i) - 1 << " = " << ParityTemp;

cout << "\tПришедший КР " << (int) pow (2.0, i) - 1 << " = " << damaged_word[(int) pow (2.0, i) - 1];

if (damaged_word[(int) pow (2.0, i) - 1] != ParityTemp) {

error_register[i] = 1;

cout << "\tНесовпадение: " << error_register[i] << endl;

} else {

error_register[i] = 0;

cout << "\tСовпадение: " << error_register[i] << endl;

}

}

// Рассчет дополнительного контрольного разряда. Если рассчитаный и

// пришедший дополнительные контрольные разряды совпали, то в регистр

// ошибок идет 0, иначе - 1

if (dmin == 4) {

ParityTemp = false;

cout << "Проверка дополнительного контрольного разряда." << endl;

for (i = 0; i < nact; i++) {

ParityTemp ^= damaged_word[i];

}

cout << "Вычисленный КР: " << ParityTemp << "\t";

cout << "Пришедший контрольный разряд: " << damaged_word[nact] << "\t";

if (damaged_word[nact] != ParityTemp) {

error_register[k] = 1;

cout << "Несовпадение: " << error_register[k] << endl;

} else {

error_register[k] = 0;

cout << "Совпадение: " << error_register[k] << endl;

}

}

return error_register;

}

bool isParityBit (int bitnum, int pb_number) {

int i = 0;

for (i = 0; i <= pb_number; i++) {

if (bitnum == (int) pow (2.0, i) - 1) {

return true;

}

}

return false;

}

int decodeErrorRegister (bitset<32> error_register, int k) {

int i = 0;

int value = 0;

for (i = 0; i < k; i++) {

if (error_register[i] == true) {

value += (int) pow (2.0, i) - 1;

}

}

return value;

}

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