69440

Код Хэмминга

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

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

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

Русский

2014-10-04

271 KB

10 чел.

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

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

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

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

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


 

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

85347. Методи корекції в системі психологічної допомоги людям з обмеженими можливостями 41.72 KB
  Одним із способів допомогти здоровим людям краще зрозуміти проблеми дітей з вадами здоровя навчитися надавати їм допомогу є програма Дитина дитині . Завданням цієї програми є навчити дітей шкільного віку та їх вчителів методам збереження свого здоровя й взаємодії з іншими дітьми особливо з тими хто має проблеми зі здоровям. Метою даної програми є допомогти дітям навчитися розрізняти різні види інвалідності і їх прояви; розуміти що незважаючи на те що людина у якої є фізичні вади може не справлятися з якоюсь роботою вона у той же...
85348. Загальні психолого-педагогічні аспекти реабілітації людини з обмеженими можливостями 35.77 KB
  Основними завданнями таких проектів психологореабілітаційного напрямку є відновлення та розвиток інтелектуальних функцій людини її емоційного стану навичок психічної саморегуляції комунікативної культури. Специфічними методами що використовуються у проектах для інвалідів є психологічні тренінги аутотренінг комунікативний тренінг тренінг креативності психотерапія ігротерапія бібліотерапія арттерапія та інше; соціальнокультурним який передбачає активізацію та розвиток творчохудожнього потенціалу дітей і дорослих засвоєння...
85349. Особливості розвитку людини з порушеннями інтелекту і психічними захворюваннями 42.36 KB
  Олігофренія одна з груп розумової відсталості різна за етіологією і патогенезом хворобливих змін обєднаних загальним клінічним проявом недорозвинення головного мозку. Олігофренія характеризується природженим або придбаним в ранньому дитинстві до 3 років загальним психічним недорозвиненням. У більшості з них спостерігалися недорозвинення мови й емоційновольова нестійкість. У структурі інтелектуального дефекту цієї групи дітей переважали недорозвинення зоровопросторових функцій труднощі встановлення послідовних умовиводів у розповідях...
85350. Депривація і особливості розвитку особистості дітей і підлітків із відхиленнями розвитку 38.99 KB
  Якщо подивитися на дітей з відхиленнями в дитинстві то емоційноособистісне спілкування з матірю не стає визначальним у розвитку дитини. Особливість психологічного статусу дитини з невеликими відхиленнями в розвитку це те що на ранньому етапі не залягали передумови становлення його психіки. Якщо не займатися з такою дитиною спеціальним розвитком і навчанням то зміни в емоційновольовій сфері дитини не відбудеться. Стрес повязаний з етапами шкільного життя з підвищенням вимог до дитини викликає певне психологічне напруження що часто...
85351. Основні завдання психологічної реабілітації людей з різними психофізичними порушеннями 39.57 KB
  Друга група завдань вивчення аномалії формування и розвитку конкретних форм психічної діяльності та її психічних процесів у різних груп аномальних дітей тобто вивчення закономірностей формування особистості розумової діяльності мови сприймання памяті. Діагностика психічного розвитку дитини містить у собі: o всебічне клінікопсихологічне вивчення особистості дитини та її батьків системи їхніх відносин; o аналіз мотиваційнопотребностної сфери дитини й членів її родини; o аналіз розвитку сенсорноперцептивних і інтелектуальних процесів...
85352. Методи корекції в системі психологічної допомоги людям із обмеженими можливостями 40.37 KB
  Розвиваючий Розвиток комунікативних навичок особистості o розвиток експресивномовленнєвих якостей; o розвиток соціальноперцептивних особистісних якостей; o розвиток інструментальних якостей. Закріплюючий Моделювання комунікативних навичок в актуальних соціальних для підлітків умовах розвиток комунікативних якостей в умовах навчальної діяльності; розвиток комунікативних якостей в сімейних умовах; розвиток комунікативних якостей в позашкільних умовах. Робота з педагогами та батьками. Просвітницький Розвиток психологічного просвітництва...
85353. Соціально-психологічні особливості людини із порушеннями слуху 40.78 KB
  Втрата слуху навіть часткова створює барєр між людиною і суспільством утруднює оволодіння знаннями і спеціальністю обмежує трудову і суспільну діяльність зтримує розвиток особистості. Відсутність слуху серйозно обмежує й естетичне виховання особи адже людина позбавляється можливості нормально сприймати музику...
85354. Компенсація, корекція і реабілітація як категорії спеціальної психології 37.42 KB
  Перша фаза виявлення того чи іншого порушення в роботі організму. Сигнал про порушення може бути повязаний і з самим розладом і з його наслідками з різними відхиленнями в поведінці і діяльності. Друга фаза оцінка параметрів порушення його локалізації та глибини виразності. Не випадково одне і те ж порушення у тварин і людини може призвести до різних наслідків.
85355. Особливості розвитку людини з порушенням зору 40.34 KB
  Вроджені: захворювання й аномалії розвитку органів зору: патологія судинної оболонки захворювання рогової оболонки ока вроджені катаракти глаукоми окремі форми патології сітківки і таке інше. Аномалії зору також можуть виникнути в результаті зовнішніх і внутрішніх негативних впливів що мали місце в період вагітності: перенесені матірю вірусні захворювання токсоплазмоз краснуха й таке інше.