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, исправляющие все одиночные ошибки.


 

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

1938. Стадии развития воспитательного коллектива. Средства формирования коллектива. Стили педагогического управления детским коллективом 22.28 KB
  Коллектив как специально организованное объединение учащихся. Процесс формирования коллектива. Стили управления детским коллективом.
1939. НОВЫЕ ПОДХОДЫ К СИНТЕЗУ ФОТОХРОМНЫХ ДИГЕТАРИЛЭТЕНОВ 1.19 MB
  Получение диарил(гетарил)ацетиленов из терминальных ацетиленов. Присоединение комплексов переходных металлов к диарилацетиленам. Попытки проведения внутримолекулярной конденсации 2,2,4,4-тетраметил-2,4-бис(2,5-диметил-3-тиенил)-3-тиапентан-1,5-диона. Синтез дитиенилэтенов с помощью внутри- и межмолекулярных конденсаций карбонильных соединений ряда тиофена по мак-мурри.
1940. Анекдот как средство переживания национальной идентичности (на материале анализа еврейских анекдотов) 1.17 MB
  Анализ теоретических и эмпирических подходов к исследованию идентичности. Изучение особенностей еврейской этнической идентичности. Социально-психологические аспекты проблемы комического. Еврейский анекдот как материал изучения еврейской национальной идентичности. Различные подходы к анализу текстов. Классификация и количественный анализ еврейских анекдотов
1941. Концепт Труд как объект идеологизации 1.17 MB
  Семантическое ядро концепта труд в русском языке, лексическое значение и концепт в научно-лингвистической интерпретации. Семантическая структура слов труд, работа. Витки идеологизации концепта труд в газете Магнитогорский рабочий.
1942. Функциональное состояние сердечно-сосудистой системы организма детей с учетом их конституциональных особенностей 1.17 MB
  Морфофункциональные особенности здоровых детей в норме и при врожденной патологии сердечно-сосудистой системы. Конституциональный подход в фундаментальной биологической характеристике целостного организма. Клиническая характеристика врожденной сердечно-сосудистой патологии. Возрастные и конституциональные особенности функционирования сердечно-сосудистой системы организма детей.
1943. Только трудом велик человек 25.02 KB
  Воспитание трудолюбия, творческого отношения к учению, труду, жизни. Ценности: уважение к труду, творчество и созидание, стремление к познанию и истине, целеустремлённость и настойчивость, бережливость, трудолюбие.
1944. Воспитательный процесс в школе 24.85 KB
  Организационно-педагогические мероприятия. Воспитание положительного отношения школьников к учению. Воспитание нравственных ценностей у школьников. Физическая культура и здоровье учащихся. Работа с родителями и общественностью.
1945. Добро починається з тебе 24.1 KB
  Мета: допомогти учням з’ясувати сутність понять добро, доброта, милосердя як принципів людського буття, навчити учнів критично ставитися до своїх вчинків та вчинків інших людей, аналізувати матеріал з різних джерел і самостійно робити правильні висновки.
1946. Воспитательные функции классного руководителя как организатора воспитательного процесса в школе 25.53 KB
  Основным структурным элементом воспитательной системы школы является класс. Именно здесь организуется познавательная деятельность, формируются социальные отношения между учащимися. Представительские функции в органах самоуправления школы реализуются также чаще всего от имени класса.