69440

Код Хэмминга

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

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

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

Русский

2014-10-04

271 KB

8 чел.

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

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

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

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

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


 

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

33002. Милетская школа. Милетская школа философии 26.78 KB
  Обратимся к наиболее известному опровержению возможности движения – знаменитым апориям Зенона которого Аристотель назвал изобретателем диалектики. Но для философа вопрос ставиться не в плоскости эмпирического существования движения а в плане мыслимости его противоречивости и в системе понятия в диалектике его соотношения с пространством и временем. Элиатам не удалось доказать что движения нет. Они своими тонкими рассуждениями показали то что едва ли кто из их современников осмысливал что такое движение Сами они в своих размышлениях...
33003. Платон и Аристотель 17.61 KB
  Философскоэтические взгляды Платона изложены в многочисленных диалогах главное действующее лицо которых как правило его учитель Сократ. В дошедших до нас произведениях нет законченной философской системы поэтому воззрения Платона на те или иные вопросы служили и продолжают служить предметом спора между исследователями. Образы идеи по мнению Платона находятся вне времени и пространства недоступны восприятию но их может созерцать разум который и связывает два мира: потусторонний и реальный. Трудно назвать область знаний которая не...
33004. Философия поздней античности 17.13 KB
  В смысловой мир человека вторгалось чувство безосновности и негарантированности существования. Именно они порабощают человека. Его основатель – Зенон из Китая утверждал что основная цель человека – жить в согласии с природой и это то же самое что жить согласно с добродетелью. Стоический мудрец идеал человека является воплощенным разумом.
33005. Философия средневековья, монотеизм как основа философии средневековья 20.82 KB
  Для философии это был период когда изменились цель и характер философствования. Философы могли свободно создавать свои мировоззренческие концепции как в области онтологии так и в гносеологии этике эстетике социальной философии. А тот факт что тенденция к союзу философии и теологии к их взаимодействию проявилась еще в конце античности...
33006. Эпоха Возрождения, этапы развития 28.3 KB
  Решающую роль при этом играло обращение к философии древних греков и римлян. В философии эпохи Возрождения мы встречаемся с оригинальными модификациями аристотелизма и платонизма стоической и эпикурейской философской мысли. Для гуманистической философии Возрождения характерно рассмотрение человека прежде всего в его земном предназначении. Первый этап развития философии эпохи Возрождения Первый этап развития философии эпохи Возрождения связан с преобладанием интереса мыслителей к проблемам устройства человека в мире который рассматривался как...
33007. Философия нового времени. Эмпиризм 17.81 KB
  Иной подход к сенсуализму продемонстрировал английский епископ Джордж Беркли 1685 1753. Стремясь защитить религию от идей материализма и атеизма Беркли в работе Трактат об основах человеческого познания 1710 использовал для этого принципы сенсуализма и в результате создал концепцию субъективного идеализма. Каждый предмет полагает Беркли можно определить как комплекс ощущений например яблоко – это собранные воедино определенный вкус цвет форма запах и пр. Все что реально существует дано нам в наших ощущениях и восприятиях...
33008. Рационализм нового времени 24.77 KB
  Рационализм можно понять как уверенность в мощи и способности разума особенно разума просвещённого руководимого правильным методом постигнуть тайны природы познать окружающий мир и самого человека с помощью здравого смысла решать практические жизненные задачи и в конечном счёте построить общество на разумных началах. И непременно с помощью разума постигать Бога. Но и Декарт Спиноза Лейбниц которых считают рационалистами также уделяли немалое внимание чувственному опыту к которому однако относились критически воле и “страстям...
33009. Философия И. Канта 28.93 KB
  Канта 22. Основные достижения философии Канта: 1. Периодизация творчества Имеет место разделение творчества Канта на докритический и критический период.: Кант находится под влиянием Лебница и разрабатывает философию как умозрительное знание.
33010. Философия Фихте и Шеллинга. Основоположения «наукоучения» в философии Фихте. Понятие «абсолютного тождества» в философии Шеллинга 25.61 KB
  Кроме того следует признать недостаточным у Канта и то что он всего лишь только описал формы мышления умственные категории и законы мысли но не выявил основного единого общего принципа познания. Ведь только наличием подобного единого общего принципа познания можно объяснить не только слаженность форм мышления умственных категорий и законов мысли но и само их внутреннее единство между собой.И это есть вопрос не только выявления недостаточности кантовской философии это вопрос концептуальный потому что задача раскрытия данного единого...