Применение алгоритмов шифрования Политики безопасности Протокол аутентификации Безопасность IP (IPSec) Использование сертификатов для обеспечения безопасности

Вычислительные сети. С ростом масштабов применения электронной вычислительной техники в научных исследованиях, проектно-конструкторских работах, управлении производством и транспортом и прочих областях стала очевидна необходимость объединения СОД, обслуживающих отдельные предприятия и коллективы.

Основы вычислительных систем

Коды Хемминга

Наиболее известные из самоконтролирующихся и самокорректирующихся кодов – коды Хемминга. Построены они применительно к двоичной системе счисления.

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

Коды Хемминга имеют бóльшую относительную избыточность, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при d = 3), либо для исправления одиночных и обнаружения без исправления двойных ошибок (d = 4). В таком коде n-значное число имеет m информационных и k контрольных разрядов. Каждый из контрольных разрядов является знаком четности для определенной группы информационных знаков слова. При декодировании производится k групповых проверок на четность. В результате каждой проверки в соответствующий разряд регистра ошибки записывается 0, если проверка была успешной, или 1, если была обнаружена нечетность.

Группы для проверки образуются таким образом, что в регистре ошибки после окончания проверки получается K-разрядное двоичное число, показывающее номер позиции ошибочного двоичного разряда. Изменение этого разряда – исправление ошибки.

Первоначально эти коды предложены Хеммингом в таком виде, при котором контрольные знаки занимают особые позиции: позиция i-го знака имеет номер 2i–1. При этом каждый контрольный знак входит лишь в одну проверку на четность.

Рассмотрим код Хемминга, предназначенный для исправления одиночных ошибок, т. е. код с минимальным кодовым расстоянием d = 3.

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

³ log2(n + 1).

(1)

Отсюда

£ n – log2(n + 1).

(2)

Значения m и k для некоторых коротких кодов, вычисленные по формулам (1) и (2) даны в табл. 7.1.

Таблица 7.1. Значения m и n

n

3

4

5

6

7

8

9

10

11

12

m

1

1

2

3

4

4

5

6

7

8

k

2

3

3

3

3

4

4

4

4

4

 

Чтобы число в регистре ошибок (РОШ) указывало номер позиции ошибочного разряда, группы для проверки выбираются по правилу:

I гр.:

 

все нечетные позиции, включая и позиции контрольного разряда, т. е. позиции, в первом младшем разряде которых стоит 1.

II гр.:

 

все позиции, номера которых в двоичном представлении имеют 1 во втором разряде справа (например, 2, 3, 6, 7, 10) и т. д.

III гр.

:

разряды, имеющие "1" в третьем разряде справа, и т. д.

Примечание: каждый контрольный знак входит только в одну проверяемую группу.

 

Пример 1. Пусть k = 5 (табл. 7.2).

Таблица 7.2. Формирование контрольных групп

Номер

проверки

Позиция

контрольного

знака

Проверяемые позиции

1

1

1, 3, 5, 7, 9, 11, 13, ...

2

2

2, 3, 6, 7, 10, 11, ...

3

4

4, 5, 6, 7, 12, 13, ...

4

8

8, 9, 10, 11, 12, 13, ...

5

16

16, 17, 18, 19, 20, 21

 

Пример 2. Рассмотрим семизначный код Хемминга, служащий для изображения чисел от 0 до 9 (табл. 7.3).

Таблица 7.3. Семизначный код Хемминга

 

Десятичное

Простой двоичный

Код Хемминга

 

число

код

 

 

 

к

 

к

к

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

1

1

1

2

0

0

1

0

0

0

1

1

0

0

1

3

0

0

1

1

0

0

1

1

1

1

0

4

0

1

0

0

0

1

0

1

0

1

0

5

0

1

0

1

0

1

0

1

1

0

1

6

0

1

1

0

0

1

1

0

0

1

1

7

0

1

1

1

0

1

1

0

1

0

0

8

1

0

0

0

1

0

0

1

0

1

1

9

1

0

0

1

1

0

0

1

1

0

0

 

Пусть передан код числа 6 в виде "0 1 1 0 0 1 1", а приняли в виде "0 1 0 0 0 1 1". Проверочные группы:

I проверка :

разряды 1, 3, 5, 7 – дает 1 в младший разряд РОШ.

II проверка :

разряды 2, 3, 6, 7 – дает 0 во второй разряд РОШ.

III проверка:

разряды 4, 5, 6, 7 – дает 1 в третий разряд РОШ.

Содержимое РОШ "101", значит ошибка в пятой позиции.

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

Вывод. Рост кодового расстояния позволяет увеличить корректирующую способность кода. В то время как d = 2 у кода с проверкой на четность позволяет обнаруживать одиночную ошибку, код Хемминга с d = 3 ис-правлет ее.

Система обработки данных (СОД) – совокупность технических средств и программного обеспечения, предназначенная для информационного обслуживания пользователей и технических объектов. В состав технических средств входит оборудование для ввода, хранения, преобразования и вывода данных, втом числе ЭВМ, устройства сопряжения ЭВМ с объектами, аппаратура передачи данных, и линии связь

Информатика, черчение, математика