69440

Код Хэмминга

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

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

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

Русский

2014-10-04

271 KB

4 чел.

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

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

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

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

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


 

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

70109. Подготовка к установке OC Windows XP в среде VirtualBox 69.5 KB
  Анализ аппаратного обеспечения ПК Определите и запишите основные технические характеристики и конфигурацию вашего ПК в виде: Тип модель процессора его тактовая частота объем кеша Тип материнской платы и ёё тактовую частоту Тип оперативной памяти ёё объем и частоту работы...
70111. ОЦЕНКА ЭФФЕКТИВНОСТИ ЗАЩИТНОГО ЗАЗЕМЛЕНИЯ 2.17 MB
  Цель работа Оценка эффективности защитного заземления в трехфазной трехпроводной сети с изолированной нейтралью и в трехфазной четырехпроводной сети с заземленной нейтралью напряжением до 1000 В. Оценить эффективность защитного заземления в трехфазной...
70112. Визначення моменту інерції тіла за періодом крутильних коливань 64 KB
  Моментом інерції матеріальної точки відносно осі обертання називається добутком маси цієї точки на квадрат відстані від осі. Моментом інерції системи (тіла) відносно осі обертання називається фізична величина, яка дорівнює сумі добутків мас n матеріальних точок на квадрати їх відстаней до даної осі...
70113. Канали з розширення спектру (DSSS, FHSS) 585.94 KB
  Приклад моделі розширення спектру однополярними сигналами з амплітудою 1 операція XOR Коди Уолша. Графік автокореляційної функції Виконати розширення спектру перемноженням двох полярних сигналів даних та коду Уолшаприклад Wlsh.
70114. ОЗНАЙОМЛЕННЯ З КОЛОРИТОМ І ТЕХНІКОЮ ВИКОНАННЯ ВИШИВОК, ВИКОРИСТАННЯ ЇХ У ПОБУТІ ТА ОДЯЗІ. РОБОТИ НАРОДНИХ МАЙСТРІВ 68 KB
  Використання домотканого полотна що має перпендикулярне переплетення ниток обумовлювало і загальний характер полтавської вишивки геометричні або геометризовані орнаментальні форми вирішені великими рельєфними масами.
70115. Текстовий процесор Microsoft Word. Робота з таблицями, графічними зображеннями та редактором формул 1010 KB
  Мета роботи:Ознайомитись з основними поняттями та принципами роботи з текстовим процесором Microsoft Word. Навчитись налаштовувати робоче середовище процесора, форматувати текст, працювати з графічними зображеннями, таблицями та підпрограмою Microsoft Equation.
70116. Формирование и развитие организаций 553.5 KB
  Факторы влияющие на развитие организаций № Факторы Способствуют Затрудняют 1 Природные ресурсы России 2 Трудовые ресурсы России 3 Территория страны 4 Национальный менталитет 5 Международные отношения 6 Государственно-политическое устройство страны...
70117. Подсчет суммы элементов квадратной матрицы, полученной из клавиатуры 55.5 KB
  Написать одну программу, с помощью которой можно задать размер квадратной матрицы. При этом размер должен быть нечётным числом и больше 7. При помощи генератора случайных чисел инициализировать матрицу целыми числами в диапазоне от -20 до +5.