Презентация на тему "Код Хэмминга"

Содержание

• 
  Слайд 1

  Код Хэмминга

• 
  Слайд 2

  История и НАЗНАЧЕНИЕ

  В середине 1940-х годов Ричард Хэмминг работал в знаменитых Лабораториях Белла на счётной машине BellModel V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машину с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую. Хэмминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перезагружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день известен как код Хэмминга. Код Хэмминга используется для обнаружения и исправления ошибок в двоичных сообщениях (в прикладных программах в области хранения данных, особенно в RAID 2);

• 
  Слайд 3

  Контрольные биты

  В исходное сообщение добавляется избыточность – контрольные биты (обозначаются как ε), которые будут контролировать правильность передачи каждого символа в сообщении. Место расположение контрольных бит в исходном определяется по формуле : № -номер (положение) №ε = 2i, где i = 0,1,2,3,4 и т.д. тогда № ε = 1,2,4,8,16,32,64,128,256 и т.д.   1 23 45 6 7 8 9 10 11 12 13 14 15 16 17 18   Формула кодового слова такова: ε0ε1а1 ε2а2 а3 а4ε3а5 а6 а7 а8 а9 а10 а11ε4   Понятно, что количество ε в кодовой последовательности зависит от количества символов в исходной. Например: в последовательности из 4 символов их 3 (ε0ε1а1 ε2а2 а3 а4 )

• 
  Слайд 4

  Матрица Хэмминга

  Используется для построения кодовой последовательности (определения значений контрольных бит), а также для проверки на стороне получателя используется проверочная матрица Хэмминга. Выбор размера матрицы зависит от количества символов в исходном сообщении. Например, если у нас исходная последовательность из 4 символов, то ε будет в количестве 3 и матрица будет (7х3) : 3– высоту матрицы определяет количество ε. (ε0, ε1, ε2 см. слайд 3), 7- количество символов с добавленными ε   0 0 0 1 1 1 1 h0 Н = 0 1 1 0 0 1 1 h1 1 0 1 0 1 0 1 h2 ε0ε1а1ε2 а2 а3 а4 1 – 001 4 – 100 7 – 111 2 – 010 5 – 101 3 – 011 6 – 110

• 
  Слайд 5

  Транспортированное кодовое слово

  1)Построение кодового слова: рассмотрим на примере Пусть дано информационное слово а = (1 0 0 1) – его надо зашифровать 1 2 3 4   То предварительно кодовое слово будет выглядеть: ε0 ε1 1 ε2 0 0 1 Далее определяем значение контрольных бит по формулам: ε0 = а1⨁ а2 ⨁а4 = 1 ⨁0 ⨁1 = 0 ε1 = а1⨁а3⨁а4 = 1 ⨁0 ⨁1 = 0 ε2 = а2⨁а3⨁а4 = 0 ⨁0 ⨁1 = 1 Составляем кодовое слово, оно будет называться транспонированноекодовое слово: Rt= 0 01 10 0 1 которое будем передавать ⨁ -XOR 1 ⨁ 1=0 0 ⨁ 0=0 1 ⨁ 0=1 1 ⨁ 0=1 a1=1, a2=0, a3=0, a4=1

• 
  Слайд 6

  Вычисление ошибки

  2)На приёмной стороне осуществляется проверка: Ошибка (синдром ошибки) вычисляется по формуле: S = H x Rt, где S- это синдром, H– проверочная матрица Хэмминга (такая же, что использовалась для построения кодовой последовательности ), Rt– принятое транспонированное кодовое слово (со слада5). Rt= 0 0 1 10 0 1 .  Итак, для того чтобы определить есть ли в принятой последовательности ошибка умножаем матрицу на строку:  h00 0 0 1 1 1 1 Н = h10 1 1 0 0 1 1 х(0 0 1 1 0 0 1) h21 0 1 0 1 0 1 ε0ε1 а1ε2 а2 а3 а4  0*0 ⨁ 0*0⨁ 0*1 ⨁ 1*1 ⨁ 1*0 ⨁ 1*0 ⨁ 1*1= 0 0*0 ⨁ 1*0 ⨁ 1*1 ⨁ 0*1 ⨁ 0*0 ⨁ 1*0 ⨁ 1*1= 0S = (000) →Значит 1*0 ⨁ 0*0⨁ 1*1 ⨁ 0*1 ⨁ 1*0 ⨁ 1*0 ⨁ 1*1= 0 ошибок нет

• 
  Слайд 7
  

  А если бы нам передали вместо 0011001 что-то вроде 0001001 У нас синдром бы получился:   0*0 ⨁0*0⨁ 0*0 ⨁1*1 ⨁ 1*0 ⨁ 1*0 ⨁1*1= 0 0*0 ⨁1*0⨁ 1*0 ⨁ 0*1 ⨁ 0*0 ⨁ 1*0 ⨁1*1= 1 S= (011) →Значит 1*0 ⨁0*0⨁ 1*0 ⨁ 0*1 ⨁ 1*0 ⨁ 1*0 ⨁1*1= 1 есть ошибка   А чтобы определить в каком из символов произошло искажение, необходимо воспользоваться проверочной матрицей Хэмминга: Найдём вычисленную комбинацию синдрома (011) в матрице – это третий символ или а1(см. слайд 6). 0001001 Можем исправить: так код двоичный, то меняем на противоположное значение 0 →1 и получаем верную комбинацию 0011001 .

• 
  Слайд 8

  Задание

  Закодируйте слово 1101. Запишите решение в отдельном файле под пунктом 1. Проверьте соответствует ли закодированное слово 1010111 исходному 1101. Запишите решение с помощью матрицы в этом же файле под пунктом 2. Закодируйте любое слово из 4 символов. Запишите решение в отдельном файле под пунктом 3. Умышленно сделайте одну ошибку.Передайте слово соседу для нахождения ошибки.