Изучение кодов защищающих от ошибок

Цель работы

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

 

2 Общие теоретические сведения

2.1 Принцип контроля с использованием корректирующих кодов

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

Для анализа свойств корректирующих кодов важное значение имеет понятие кодового расстояния. Под ним понимают количество разрядов, в которых значения одного слова отличаются от значений другого слова. В общем виде кодовое расстояние между словами A_i и A_j выражается формулой

где - значение k-го разряда в слове A_i;

- символ сложения по модулю 2.

Для каждого кода существует минимальное кодовое расстояние d =min(d_ij), которое определяет свойства этого кода.

Известна следующая зависимость между числом обнаруживаемых ошибок t и минимальным кодовым расстоянием d ≥ t +1.

Для того, чтобы код обеспечил исправление t ошибок, его минимальное кодовое расстояние должно удовлетворять условию d ≥ 2 t +l.

Минимальное кодовое расстояние определяется избыточностью кода, под которой понимают отношение числа m контрольных разрядов к числу ин­формационных n: d = m / n.

 

2.2 Код с проверкой на четность

Пусть требуется передать информационный набор а₁..а_k Кодовый набор получается в результате дописывания к последовательности символа а_k+1, который назначается так, чтобы число единиц в последовательности а₁..а_kа_k+1 было четным. Если при передаче произошла одна ошибка, то число единиц в принятом наборе b₁..b_kb_k+1 станет нечетным. Это и указывает на наличие ошибки. Место ошибки найти не удается, поэтому декодирование не производится. Таким образом, код с проверкой на четность обнаруживает (но не ис­правляет) одну ошибку. Он также обнаруживает любое нечетное число ошибок.

Кодовые слова а₁..а_kа_k+1содержат четное число единиц, поэтому для них справедливо соотношение

которое называется проверочным.

2.3 Код Хэмминга для исправления одиночных ошибок

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

Каждый разряд слова включается в несколько подмножеств. Номера контрольных разрядов определяются из соотношения .

В таблице 1 звездочками показано расположение контрольных разрядов в 15-разрядном слове.

 

Таблица 1

Номера разрядов

Контрольные разряды

*

*

*

*

 

Формирование подмножеств производится на основе анализа номера разряда при записи его в.двоичной системе счисления. Все разряды кодового слова, имеющие единицу в первом разряде своего номера, включаются в первое подмножество, во втором - во второе и т.д. Затем подсчитывается количество единиц в разрядах, относящихся к каждому подмножеству, и в соответствующий контрольный разряд записывается единица, если это количество нечетно, и нулю - если четно.

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

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

 

Таблица 2

Номер кодового слова	Подмножество
десятичный	двоичный
		*
			*
		*	*
				*
		*		*
			*	*
		*	*	*
					*
		*			*
			*		*
		*	*		*
				*	*
		*		*	*
			*	*	*
		*	*	*	*

2.4 Код Хэмминга для исправления одиночных ошибок и обнаружении двойных ошибок

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

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

2.5 Циклические коды

Для того, чтобы произвести математическое описание и исследование циклических кодов, каждому двоично-кодированному п-разрядному слову ставится в соответствие полином (n-1)-й степени переменной х, причем коэффици­ентами полинома являются значения соответствующих разрядов слова.

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

Кодирование информационной части слова, представленной полиномом G(x), происходит в соответствии с соотношением

где R(x) - остаток от деления G(x) х^k на порождающий полином P(х) степени k.

Существо кодирования состоит в следующем. Информационная часть слова за счет умножения G(x) на х^k сдвигается на k разрядов влево. В освободившиеся k младших (контрольных) разрядов записывается остаток R(x) от де­ления G(x) х^k на Р(х), который и представляет контрольную часть слова.

Получение контрольной части слова, соответствующей полиному R(x), практически осуществляется путем последовательного вычитания (сложения) по модулю 2 из сдвинутой информационной части слова другого слова, соответствующего порождающему полиному Р(х).

 

3 Порядок выполнения работы

1. Ознакомиться с теоретической частью к лабораторной работе.

2. Представить алгоритмы, по которым происходит кодирование переда­ваемого сообщения с использованием кодов представленных в 2.2...2.5 на пере­дающей стороне.

3. Представить алгоритмы, по которым происходит декодирование принимаемого сообщения с использованием кодов, представленных в 2.2…2.5 на приемной стороне.

4. Написать программу по пункту 1 для передаваемого сообщения (приложение А) с использованием алфавита кода КОИ-7 (приложение Б).

5. Написать программу по п.2 для принимаемого сообщения (приложение А) с использованием алфавита кода КОИ-7 (приложение Б).

6. Исследовать канал передачи сообщения при наличии одной ошибки в передаваемом сообщении (приложение В) с использованием кодов, представленных в пунктах 2.2...2.5.

7. Исследовать канал передачи сообщения при наличии двух ошибок в передаваемом сообщении (приложение В) с использованием кодов, представленных в 2.2...2.5.

8. Исследовать канал передачи сообщения при наличии трех ошибок в передаваемом сообщении (приложение В) с использованием кодов, представленных в 2.2...2.5.

9. Представить отчет.

Примечание. Для циклического кода использовать порождающий полином Р(х) = х³+х+1.

4 Требования к отчету

Отчет по лабораторной работе должен содержать:

а) титульный лист;

б) алгоритмы кодирования передаваемого сообщения с использованием кода проверки на четность, кода Хэмминга для исправления одиночных оши­бок, кода Хемминга для исправления одиночных ошибок и обнаружения двой­ных, а также циклических кодов;

в) алгоритмы декодирования принимаемого сообщения с использовани­ем кода проверки на четность, кода Хэмминга для исправления одиночных ошибок, кода Хемминга для исправления одиночных ошибок и обнаружения двойных, а также циклических кодов;

г) переданное сообщение;

д) результаты приема сообщения на приемной стороне с использовани­ем кода проверки на четность, кода Хэмминга для исправления одиночных ошибок, кода Хемминга для исправления одиночных ошибок и обнаружения двойных, а также циклических кодов при наличии в сообщении одной ошиб­ки;

е) результаты приема сообщения на приемной стороне с использовани­ем кода проверки на четность, кода Хэмминга для исправления одиночных ошибок, кода Хемминга для исправления одиночных ошибок и обнаружения двойных, а также циклических кодов при наличии в сообщении двух ошибок;

ж) результаты приема сообщения па приемной стороне с использовани­ем кода проверки на четность, кода Хэмминга для исправления одиночных ошибок, кода Хемминга для исправления одиночных ошибок и обнаружения двойных, а также циклических кодов при наличии в сообщении трех ошибок;

з) выводы по пунктам д) е) и ж).

 

5 Контрольные вопросы

1. Дайте определение корректирующего кода.

2. Что понимают под кодовым расстоянием корректирующего кода.

3. Приведите алгоритм кодирования/декодирования передаваемой/ принимаемой информации при использовании кода с проверкой на четность.

4. Приведите алгоритм кодирования/декодирования передаваемой/ принимаемой информации при использовании кода Хэмминга для исправления одиночных ошибок.

5. Приведите алгоритм кодирования/декодирования передаваемой/принимаемой информации при использовании кода Хэмминга для исправ­ления одиночных ошибок и обнаружения двойных.

6. Приведите алгоритм кодирования/декодирования передаваемой/ принимаемой информации при использовании циклических кодов.