16.3. КОД ХЭММИНГА




Hamming

Построение Кода Хэмминга:

Основная идея кодов Хэмминга - что бы исправить ошибку надо как
минимум иметь столько проверочных бит что бы можно было адрессовать
все биты данных + проверочные биты.


bit	  9   8   7   6   5   4   3   2   1
	+---+---+---+---+---+---+---+---+---+      +---+
	|   |XXX|   |   |   |XXX|   |XXX|XXX|      |ZZZ|
	+---+---+---+---+---+---+---+---+---+      +---+
	     p4  a3  a2  a1  p3  a0  p2  p1         p
		

	1. Контрольные разряды занимают места с позицией 2**N (N=0..)
	2. В свободные места кладутся данные
	3. p1 покрывает разряды ai с позициями XXXXX1 (1,3,5,7,9...)
	   p2 покрывает разряды ai с позициями XXXX1X (2,3,6,7,10,11,..)
	   p3 покрывает разряды ai с позициями XXX1XX (4,5,6,7,12,13,14,15,..)
	   (имеются в виду разряды в этой сетке, смотрятся только
	    разряды данных)

	4. Еще иногда есть p которое общее для всей кодовой комбинации
	   p = a0 (+) ... (+) aN (+) p1 (+) ... (+) pM


	Код Хэмминга X/Y - означает:
		X/Y =  Общая длинна/Число разрядов данных.


    p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 d8 d9 d10 d11 p5 d12 d13 d14 d15 d16 d17 d18
p1  X     X     X     X     X     X     X      X      X       X       X        X
p2     X  X        X  X        X  X        X   X          X   X            X   X
p3           X  X  X  X              X  X  X   X                   X  X    X   X
p4                       X  X  X  X  X  X  X   X
p5                                                 X  X   X   X    X  X    X   X2




Код Хэмминга 7/4 (8/4)

Код Хэмминга 7/4 (8/4) 7/4 - это без p (distance = 3) исправляет одиночные 8/4 - это с p (distance = 4) исправляет одиночные + обнаруживает двойные ----------------------------------------------------------- p a3 a2 a1 p3 a0 p2 p1 ----------------------------------------------------------- -+ 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 1 1 | 1 0 0 1 1 0 0 1 | 0 0 0 1 1 1 1 0 | 1 0 1 0 1 0 1 0 | 0 0 1 0 1 1 0 1 | 0 0 1 1 0 0 1 1 | 1 0 1 1 0 1 0 0 + 0 1 0 0 1 0 1 1 + симметрия 1 1 0 0 1 1 0 0 | 1 1 0 1 0 0 1 0 | 0 1 0 1 0 1 0 1 | 1 1 1 0 0 0 0 1 | 0 1 1 0 0 1 1 0 | 0 1 1 1 1 0 0 0 | 1 1 1 1 1 1 1 1 | ----------------------------------------------------------- -+ p1 = a0 (+) a1 (+) a3 p2 = a0 (+) a2 (+) a3 p3 = a1 (+) a2 (+) a3


Наглядный пример кода хэмминга: Это 4 бита данных которые надо защищать:



Добавляем биты четности так, что бы в каждой окружности было четное число единичных битов. (Это код Хэмминга 7/4)



Синдромы одиночной ошибки:

Добавляем теперь бит общей четности получаем код Хэмминга 8/4:














Пример кодера в код Хэмминга 8/4:



Пример кодера в код Хэмминга 8/4: library ieee; use IEEE.std_logic_1164.ALL; ENTITY hamenc IS port( datain : IN BIT_VECTOR(0 TO 3); --d0 d1 d2 d3 hamout : OUT BIT_VECTOR(0 TO 7)--d0 d1 d2 d3 p0 p1 p2 p4 ); END hamenc; ARCHITECTURE arch OF hamenc IS signal p0, p1, p2, p4 : BIT; --check bits BEGIN --generate check bits p0 <= (datain(0) XOR datain(1)) XOR datain(2); p1 <= (datain(0) XOR datain(1)) XOR datain(3); p2 <= (datain(0) XOR datain(2)) XOR datain(3); p4 <= (datain(1) XOR datain(2)) XOR datain(3); --connect up outputs hamout(4 TO 7) <= (p0, p1, p2, p4); hamout(0 TO 3) <= datain(0 TO 3); END arch;


Декодирование: Исправление одиночных ошибок: p p3 p2 p1 - - - - нет ошибки E - - - ошибка в p E - - E ошибка в p1 E - E - ошибка в p2 E - E E ошибка в a0 E E - - ошибка в p3 E E - E ошибка в a1 E E E - ошибка в a2 E E E E ошибка в a3 - X X X двойная ошибка (XXX != ---) (- нет ошибки, E - ошибка) Пример декодера с исправлением одиночных ошибок из кода Хэмминга 8/4.



Пример декодера из кода Хэмминга 8/4: library ieee; use IEEE.std_logic_1164.ALL; ENTITY hamdec IS PORT( hamin : IN BIT_VECTOR(0 TO 7); --d0 d1 d2 d3 p0 p1 p2 p4 dataout : OUT BIT_VECTOR(0 TO 3); --d0 d1 d2 d3 sec, ded, ne : OUT BIT); --diagnostic outputs END hamdec; ARCHITECTURE arch OF hamdec IS BEGIN PROCESS(hamin) VARIABLE syndrome : BIT_VECTOR(3 DOWNTO 0); BEGIN --generate syndrome bits syndrome(0) := (((((((hamin(0) XOR hamin(1)) XOR hamin(2)) XOR hamin(3)) XOR hamin(4)) XOR hamin(5)) XOR hamin(6)) XOR hamin(7)); syndrome(1) := (((hamin(0) XOR hamin(1)) XOR hamin(3)) XOR hamin(5)); syndrome(2) := (((hamin(0) XOR hamin(2)) XOR hamin(3)) XOR hamin(6)); syndrome(3) := (((hamin(1) XOR hamin(2)) XOR hamin(3)) XOR hamin(7)); IF (syndrome = "0000") THEN --no errors ne <= '1'; ded <= '0'; sec <= '0'; dataout(0 TO 3) <= hamin(0 TO 3); ELSIF (syndrome(0) = '1') THEN --single bit error ne <= '0'; ded <= '0'; sec <= '1'; CASE syndrome(3 DOWNTO 1) IS WHEN "000"|"001"|"010"|"100" => dataout(0 TO 3) <= hamin(0 TO 3); -- parity errors WHEN "011" => dataout(0) <= NOT hamin(0); dataout(1 TO 3) <= hamin(1 TO 3); WHEN "101" => dataout(1) <= NOT hamin(1); dataout(0) <= hamin(0); dataout(2 TO 3) <= hamin(2 TO 3); WHEN "110" => dataout(2) <= NOT hamin(2); dataout(3) <= hamin(3); dataout(0 TO 1) <= hamin(0 TO 1); WHEN "111" => dataout(3) <= NOT hamin(3); dataout(0 TO 2) <= hamin(0 TO 2); END CASE; --double error ELSIF (syndrome(0) = '0') AND (syndrome(3 DOWNTO 1) /= "000") THEN ne <= '0'; ded <= '1'; sec <= '0'; dataout(0 TO 3) <= "0000"; END IF; END PROCESS; END arch;


Порождающая матрица для систематического кода Хэмминга (7,4) | 1 0 0 0 0 1 1 | | 0 1 0 0 1 0 1 | | 0 0 1 0 1 1 0 | | 0 0 0 1 1 1 1 | Собственно возможен и несистематический код Хэмминга (7,4) вот для него пораждающая матрица | 1 1 0 1 0 0 0 | | 0 1 1 0 1 0 0 | | 0 0 1 1 0 1 0 | | 0 0 0 1 1 0 1 |


Проверочная матрица для систематического кода Хэмминга (7,4) | 1 1 0 1 1 0 0 | H = | 0 1 1 1 0 1 0 | | 1 0 1 1 0 0 1 | |1| |0| H * |0| |1| |0| = |0| |0| |1| синдром |0| |0| кодовая комбинация (в частности лидер смежного класса - показывает где ошибка) имеет наименьшее количество нулей Если синдром = 0, то ошибки нет Соответсвенно: --------------------------- Синдром Коррекция --------------------------- 000 0000000 001 0000001 010 0000010 011 0010000 100 0000100 101 1000000 110 0100000 111 0001000 ---------------------------


Код Хэмминга 11/7



------------------------ p1 p2 p3 p4 error bit ------------------------ E E + + d1 E + E + d2 + E E + d3 E E E + d4 E + + E d5 + E + E d6 E E + E d7 E + + + p1 + E + + p2 + + E + p3 + + + E p4 + + + + no errors ------------------------ остальные синдромы - это уже множественные ошибки. 11/7 - Естественно может только исправлять одиночные ошибки. Например если двойная ошибка в d1 и d2 то имеем: ------------------------ p1 p2 p3 p4 --------------------- + E E + - как будто ошибка в d3. ------------------------ Если добавить еще один бит общей четности то будет 12/7 - он сможет еще и находить двойные ошибки.


Код Хэмминга 15/5

Hamming(15,5) Порождающая матрица | 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 | | 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 | | 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 | | 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 | | 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 |


Длинна кодов Хэмминга

Полная длинна Длинна данных Для исправления одиночных ошибок: 2**M - 1 2**M - 1 - M Для исправления одиночных и обнаружения двойных: 2**M 2**M - 1 - M (M - число проверочных символов) Код Хэмминга - это абсолютный минимум, код меньшей длинны с такими свойствами построить нельзя. - distance 3 - - distance 4 - Info Control Total Control Total bits bis bits bits bits 1 2 3 3 4 <=4 3 <=7 4 <=8 <=11 4 <=15 5 <=16 <=26 5 <=31 6 <=32 <=57 6 <=63 7 <=64 <=120 7 <=127 8 <=128

Index Prev Next