Hamming Code 이근용

2 Error Control Error Detection Parity Check CRC Check Error Correction Hamming Code

3 오류 검출과 교정 송신측에서 원래의 데이터에 여분의 메 시지를 추가하여 수신측에서 메시지의 에러를 검출하거나 교정할 수 있도록 하 는 것

4 SymbolOriginal CodeCode with redundant A B C D E F G H If 1bit error (B) 0101 (C) 1001 (E)

5 BER(Bit Error Rate)  에러가 없이 전송될 확률 : p 전송할 때 에러 발생확률 : q = 1-p 3digit 의 메시지 에러 없이 전송될 확률 : p 3 에러가 하나 발생 : 3p 2 q  000  001, 010, 100 에러가 두개 발생 : 3pq 2 에러가 세개 발생 : q 3

6 BER n binary digit 에서 r 개의 오류가 발생할 확률 -

7 Hamming Code (1) 오류 검출 및 정정이 가능한 코드 Parity Digit 라고 불리는 여분의 코드를 가지고 있음 Message 길이가 n digits long 이고 정보를 표현하는데 m digits(m < n) 라면, 검출과, 정정을 위해서 사용된 코드  K = n-m

8 Hamming Code (2) Single error detection n-1 까지 message n 번째 parity Hamming 은 parity check 에 기초하여 검 출및 정정이 가능한 코드를 만들었음 에러가 발생한 위치 파악 가능

9 Hamming Code (3) Definition 1 Let x= and y = be n- tuples representing messages x 1 x 2, …,x n and y 1,y 2, …,y n respectively, where x i, y i in {0,1}, The Hamming distance between x and y, denoted by H(x,y), is the number of coordinates for which all x i and y i are different. Cleary

10 Hamming Code (4) For example and is 3 x, y, z in S n H(x,y) >= 9 H(x,y) = 0  x = y H(x,y) = H(y,x) H(x,y) + H(y,z) >= H(x,z)

11 Hamming Code(5) Definition 2 The minimum distance of a code, whose words are n-tuples, is the minimum of the Hamming distance between all pairs of code words in the code. Example  X = H(x,y)=3  Y = H(y,z)=2  Z = H(x,z)=1  Minimum distance in this code is 1

12 Hamming code(6) Theorem 1 A code can detect all combinations of k or fewer errors if and only if the minimum distance between any two code words is at least k+1

13 Hamming code (7) Theorem 2 A code can correct all combinations of k or fewer errors if and if the minimum distance between any two code words is at least 2k+1

14 Hamming code 설계 1 개 또는 2 개의 오류 검출 1 개의 오류 정정 m = 4, k = 3  x 1 +x 2 +x 3 +x 5 = 0 (1), x 5 = -(x 1 +x 2 +x 3 ), x 5 = (x 1 +x 2 +x 3 )  x 1 +x 2 +x 4 +x 6 = 0 (2), x 6 = -(x 1 +x 2 +x 4 ), x 6 = (x 1 +x 2 +x 4 )  x 1 +x 3 +x 4 +x 7 = 0 (3), x 7 = -(x 1 +x 3 +x 4 ), x 7 = (x 1 +x 3 +x 4 ) All mod 2

15 x 1 x 2 x 3 x 4 x 5 x 6 x x 5 = (x 1 +x 2 +x 3 ) x 6 = (x 1 +x 2 +x 4 ) x 7 = (x 1 +x 3 +x 4 ) All mod 2

16 Hamming code Error Detect (1),(2),(3) 을 각각 P 1, P 2, P 3 를 true 로 만 들면 Error 발생  P 1 = ( ) mod 2 = 1  Error  P 2 = ( ) mod 2 = 0  P 3 = ( ) mod 2 = 0 Error 위치 x  P 1, P 2, P 3 Error  x 1 Error

17 Error Position Detect S1S1 S2S2 S3S3 (1),(2),(3) 을 각각 S 1,S2,S3 라하면 5  S 1 and ~S 2 and ~S 3 2  S 1 and S 2 and ~S 3 6  ~S 1 and S 2 and ~S 3 3  S 1 and ~S 2 and S 3 7  ~S 1 and ~S 2 and S 3 1  S 1 and S 2 and S 3 4  ~S 1 and S 2 and S 3

18 Error Position Detect Proposition P1 P2 P3 Incorrect Digit None X x 5 X x 6 X x 7 X X x 2 X X x 3 X X x 4 X X X x 1

19 참고도서 Discrete Mathmatical Structures with Applications to Computer Science J.P. TREMBLAY, R. MANOHAR McGRAW-HILL BOOK COMPANY, 1975 Data and Computer Communications fourth edition William Stallings, PH.D. MACMILLAN PUBLISHING COMPANY, 1994