69440

Код Хэмминга

Лабораторная работа

Информатика, кибернетика и программирование

Формирование r проверочных элементов в комбинации этого кода осуществляется по k информационным элементам. Таким образом длина кодовой комбинации n = r k. Проверочные элементы представляют собой линейные комбинации информационных элементов т.

Русский

2014-10-04

271 KB

9 чел.

Министерство науки и образования Украины

Университет развития человека „Украина

Отчет по лабораторной работе
Дисциплина "Теория информации и кодирования"
Тема:
Код Хэмминга

Принял: Вишталь

Выполнил:
студент 3  курса гр. КС-31
Гребинь Д. А.

Киев 2005

Лабораторная работа № 8

Тема:  Код Хэмминга

Цель:  Изучить код Хэмминга, выяснить особенности его построения и  применения

Краткие теоретические сведения

    Код Хэмминга – один из наиболее распространенных систематических кодов. К кодам Хэмминга относятся коды с минимальным кодовым расстоянием dmin = 3, исправляющие все одиночные ошибки.

    Формирование r проверочных элементов в комбинации этого кода осуществляется по k информационным элементам. Таким образом, длина кодовой комбинации n = r + k. Проверочные элементы представляют собой линейные комбинации информационных элементов, т.е. взвешенные суммы информационных элементов с весовыми коэффициентами 1 и 0. Для двоичных кодов в качестве линейной операции используют сложение по модулю 2. Операция вычитания совпадает с операцией сложения.

    Последовательность 0 и 1 в кодовой комбинации иначе называют кодовым вектором. Коду Хэмминга присущи свойства линейных кодов:

  1.  Сумма или разность кодовых комбинаций кода дает вектор, принадлежащий данному коду.
  2.  Линейные коды образуют алгебраическую группу по отношению к операции сложения по модулю 2.
  3.  Минимальое кодовое расстояние между кодовыми векторами группового кода равно минимальному весу ненулевых кодовых векторов.

    При передаче кодового вектора может быть искажен любой элемент, число таких ситуаций равно C1n = n. К этому следует добавить еще одну ситуацию, когда ошибка не произошла. Таким образом, общее число комбинаций проверочных элементов 2r должно превышать число возможных ошибочных ситуаций в коде с учетом отсутствия ошибок для правильного их различия и определения мест ошибок: 2r >= n + 1. Поскольку 2n = 2r+k = 2k2r, можно записать: 2n >= ( n + 1 ) 2k, где 2n – полное число комбинаций кода.

    Минимальное соотношение корректирующих и информационных разрядов, ниже которого код не может сохранять свои корректирующие способности, определяется из выражения 2r - 1 = n.

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

r

2

3

3

3

3

4

4

4

4

4

4

4

4

5

n

3

4

5

6

7

8

9

10

11

12

13

14

15

16

k

1

1

2

3

4

4

5

6

7

8

9

10

11

11

    Характерной особенностью проверочной матрицы кода с dmin = 3 является то, что ее столбцы представляют собой различные ненулевые комбинации длиной r. Например, при r = 4 и n = 15, код (15, 11), проверочная матрица имеет вид:

H15,11 =

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

u1

u2

u3

u4

u5

u6

u7

u8

u9

u10

u11

u12

u13

u14

u15

    Итак, если взять комбинации простого четырехэлементного кода и отбросить нулевыю комбинацию, то можно легко получить проверочную матрицу, записав все кодовые комбинации последовательно в столбцы матрицы H.

    Перестановкой столбцов, содержащих одну единицу, вправо матрицу приводим к виду:

H15,11 =

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

0

0

0

1

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

1

1

0

0

1

0

1

1

0

1

1

0

1

0

1

0

1

0

0

0

1

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

a15

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

b1 =

a5 (+)

a6 (+)

a7 (+)

a8 (+)

a9 (+)

a10 (+)

a11

b2 =

a2 (+)

a3 (+)

a4 (+)

a8 (+)

a9 (+)

a10 (+)

a11

b3 =

a1 (+)

a3 (+)

a4 (+)

a6 (+)

a7 (+)

a10 (+)

a11

b4 =

a1 (+)

a2 (+)

a4 (+)

a5 (+)

a7 (+)

a9  (+)

a11

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

    Так, если ошибка возникла в 7-м информационном разряде, то окажутся невыполненными 1, 3 и 4 уравнения, т.е синдром равен 1011 (совпадает с 7-м столбцом матрицы H). Таким образом, местоположение столбца матрицы H, совпадающего с вычисленным синдромом, указывает место ошибки. Вычисленное значение синдрома обязательно совпадает с одним из столбцов матрицы H, т.к. в качестве столбцов выбраны все возможные двоичные r-разрядные числа.

    Хэмминг предложил расположить столбцы проверочной матрицы так, чтобы номер i-го столбца матрицы H и номер ошибочного разряда кодовой комбинации соответствовали двоичному представлению числа i. Тогда синдром, полученный из проверочных уравнений, будет двоичным представлением номера разряда кодовой комбинации, в котором произошла ошибка. Для этого проверочные разряды должны находиться не в конце кодовой комбинации, а на номерах позиций, которые выражаются степенью двойки ( 20, 21, 22, ... 2r-1 ), как это имеет место в непреобразованной матрице H, потому что каждый из них входит только в одно из проверочных уравнений.

    В последнем случае проверочные разряды размещаются между информационными. Синдром, согласно непреобразованной проверочной матрице H15,11, определяется из уравнений:

S1 =

u1

(+) u3 

(+) u5 

(+) u7 

(+) u9 

(+) u11 

(+) u13

(+) u15

S2 =

u2 

(+) u3 

(+) u6 

(+) u7 

(+) u10 

(+) u11 

(+) u14

(+) u15

S3 =

u4 

(+) u5 

(+) u6 

(+) u7 

(+) u12 

(+) u13 

(+) u14

(+) u15

S4 =

u8 

(+) u9 

(+) u10 

(+) u11 

(+) u12 

(+) u13 

(+) u14

(+) u15

    В качестве проверочных выбирают разряды u1, u2, u4 и u8, которые  встречаются  в этой системе уравнений по одному разу.

    Например, если необходимо  закодировать сообщение простого кода 11001010110 ( k = 11 ) в коде Хэмминга, нужно определить проверочные разряды в комбинации: u1 u2 1 u4 100 u8 1010110. Из проверочной матрицы получаем:

u1 =

u3 

(+) u5 

(+) u7 

(+) u9 

(+) u11 

(+) u13

(+) u15

u2 =

u3 

(+) u6 

(+) u7 

(+) u10 

(+) u11 

(+) u14

(+) u15

u4 =

u5 

(+) u6 

(+) u7 

(+) u12 

(+) u13 

(+) u14

(+) u15

u8 =

u9 

(+) u10 

(+) u11 

(+) u12 

(+) u13 

(+) u14

(+) u15

    Вычисляя проверочные разряды согласно этой системе, получим для данного сообщения:

u1 = 1 (+) 1 (+) 0 (+) 1 (+) 1 (+) 1 (+) 0 = 1,
u
2 = 1 (+) 0 (+) 0 (+) 0 (+) 1 (+) 1 (+) 0 = 1,
u
4 = 1 (+) 0 (+) 0 (+) 0 (+) 1 (+) 1 (+) 0 = 1,
u
8 = 1 (+) 0 (+) 1 (+) 0 (+) 1 (+) 1 (+) 0 = 1.

    Следовательно, комбинация кода Хэмминга для рассматриваемого сообщения будет иметь вид 111110001010110.

    Предположим, что 8-й єлемент кодовой комбинации принят ошибочно, т.е. получено сообщение 111110011010110. Вычисляя синдром, получим: S1 = 0; S2 = 0; S3 = 0; S4 = 1,  т.е. синдром имеет вид 10002 = 810 (очевидно, что для получения правильного результата биты синдрома необходимо записать, начиная со старшего, т.е. S4S3S2S1). Таким образом, необходимо исправить 8-й разряд кодовой принятой комбинации.

Вывод: Код Хэмминга – один из наиболее распространенных систематических кодов. К кодам Хэмминга относятся коды с минимальным кодовым расстоянием dmin = 3, исправляющие все одиночные ошибки.


 

А также другие работы, которые могут Вас заинтересовать

44290. Rомп'ютеризованf видавничу систему 882.5 KB
  Порівняльні характеристики деяких мікропроцесорів Процесори Характеристики Celeron D Pentium 4 Pentium 4 D Частота МГц 2533 3000 3200 Розєм LG775 LG775 LG775 Кешпамять 2 рівня Кб 256 2048 22048 Частота системної шини МГц 533 800 800 Ціна грн 383 1037 2408 Для робочих станцій оброблення текстової інформації РС1 РС2 не потрібний дуже потужний процесор тому згідно таблиці 2 ми обираємо найкращій варіант по співвідношенню: ціна швидкодія. Найважливіші параметри окремих моделей дисплеїв деяких фірм з діагоналлю екрана 17 Дисплей...
44292. Анализ правоприменительной практики, теоретических, правовых и организационных аспектов возбуждения уголовных дел 392.5 KB
  Понятие модели и значение стадии возбуждения уголовного дела. Понятие и сущность стадии возбуждения дела. Задачи и значение стадии возбуждения дела. Поводы основания и процессуальный порядок возбуждения уголовного дела.
44293. Технологический процесс технического обслуживания и ремонта раздаточной коробки передач 707.5 KB
  Технологический процесс технического обслуживания и ремонта раздаточной коробки передач.3 Производственная санитария и гигиена труда ЗАКЛЮЧЕНИЕ Письменная экзаменационная работа Техническое обслуживание и ремонт раздаточной коробки передач.
44294. ВДОСКОНАЛЕННЯ МЕХАНІЗМУ ТРАНСПОРТНО-ЛОГІСТИЧНОГО ОБСЛУГОВУВАННЯ МІЖНАРОДНИХ ВАНТАЖНИХ ПЕРЕВЕЗЕНЬ 1.62 MB
  Теоретичною та методологічною основою дипломної роботи являються наукові дослідження вітчизняних та зарубіжних вчених, присвячені удосконаленню транспортно-логістичного обслуговування та проблематиці впровадження логістичних структур у національну систему транспортно-логістичної інфраструктури
44295. Фреттинг-коррозия титановых сплавов 6.37 MB
  По своей коррозионной стойкости в морской воде он превосходит все металлы, за исключением благородных – золота, платины и т. п., большинство видов нержавеющей стали, никелевые, медные и другие сплавы. В воде, во многих агрессивных средах чистый титан не подвержен коррозии.
44296. Разработка Web- приложения «Такси«Люкс» 1.61 MB
  База данных представляет собой структурированную совокупность данных. Эти данные могут быть любыми-от простого списка предстоящих покупок до перечня экспонатов картинной галереи или огромного количества информации в корпоративной сети
44297. Анализ взаимосвязи социально-психологической адаптации и агрессивности у детей, проживающих в детском доме и семье 315 KB
  Социально-психологические особенности детей проживающих в детском доме и семье . Организация и методы исследования по выявлению взаимосвязи социально-психологической адаптации и агрессивности у детей проживающих в детском доме и семье . Проблема социально-психологической адаптации детей воспитывающихся в детском доме имеет свои особенности которые требуют подробного изучения. Что касается детей проживающих и воспитывающихся в семье то здесь также существует проблема социально-психологической адаптации и...
44298. Исследование процесса волнового диспергирования газа в жидкости 7.52 MB
  Полученные результаты Рисунок 2  Зависимость расхода воды через диспергатор от давления воды 1  внутренняя подача газа dк=7 мм dотв=28 мм диспергатор старого поколения; 2  внешняя подача газа dк=5 мм dотв=20 мм диспергатор нового поколения Рисунок 3  Пример обрабатываемой фотографии с отмеченной базовой линией Рисунок 4  Вид экрана компьютера в процессе обработки фотографии Рисунок 5  Зависимость среднего диаметра воздушных пузырьков от давления воды на выходе из насоса при расходе воздуха Qг = 05...