Код Хэмминга 7/4 (8/4)
Наглядный пример кода хэмминга: Это 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