[algospot]HAMMINGCODE

문제

https://algospot.com/judge/problem/read/HAMMINGCODE

 

해밍코드(http://ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%8D_%EB%B6%80%ED%98%B8)

해밍코드란 리처드 해밍이 제안한 오류정정코드다. 보통 해밍코드라고하면  (7,4)해밍코드를 뜻한다.

(7,4)해밍코드는 4비트 데이터비트와 3비트의 패리티비트로 이루어진다.

좀더 알아보기위해서 1000을 해밍코드로 변환해보자. 7비트중에 패리티비트의 위치는 2의거듭재곱번째 위치에 있는 비트가 패리티 비트가 된다. 

1	2	3	4	5	6	7
2^0자리	2^1자리		2^2자리
		1		0	0	0

위의 표와같이 메세지 1000을 배치한 후에 패리티비트를 채워준다.

1 : 1자리부터 시작해서 1비트 검사하고 1비트 건너뛰기를 반복한다. 1,3,5,7 자리 xor 한 결과는 1^0^0^ = 1

2 : 2자리부터 시작해서 2bit검사하고 2bit건너뛰기를 반복한다.2,3,6,7 자리 xor 한 결과는 1^0^0 = 1

4 : 4자리부터 시작해서 4bit검사한다. 건너뛸비트가 없다 끝이다. 4,5,6,7 자리  xor 한 결과는 0^0^0 = 0

 

만들어진 해밍코드는 1110000 ~~

 

자 이제 오류검출게임을 시작하지~

1110000을 보냈지만 받은사람이 3번째 자리가 잘못된 1100000을 받았다고 가정하고 오류검출을 해보자.

위에서 패리티 비트 만들었던 것과 순서는 같다.

1 : 1자리부터 시작해서 1비트 검사하고 1비트 건너뛰기를 반복한다. 1,3,5,7 자리 xor 한 결과는 1^0^0^0 = 1

2 : 2자리부터 시작해서 2bit검사하고 2bit건너뛰기를 반복한다.2,3,6,7 자리 xor 한 결과는 1^0^0^0 = 1

4 : 4자리부터 시작해서 4bit검사한다. 건너뛸비트가 없다 끝이다. 4,5,6,7 자리  xor 한 결과는 0^0^0^0 = 0

 

각 결과 값들을 2진수로 나열했을 때 011이 된다.10진수로 3이되고 3번째 bit가 잘못되었다고 검출되었다.~정답

 

입력

7비트 해밍코드

 

출력

올바른 데이터 검출 4bit

 

풀이

7bit 값을 입력받아서 시프트연산을 통해서 패리티비트를 구해낸다음에 결과값을 나열해서 0이 아니면

결과값이 가리키는 자릿수의 bit를 반전해준다. 

 

 

package com.tutorial;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class HAMMINGCODE {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System. in));
        int cnt = Integer.parseInt(br.readLine());
        while (cnt -- > 0) {
            hcode h = new hcode(br.readLine());
            h.check();
            System.out.println(h.getData());
        }
    }
}
class hcode {
    private int n;
    private char[] s;
    public hcode(String a) {
        this.s = a.toCharArray();
        this.n = Integer.valueOf(a, 2);
    }
    public void check() {
        String check = "";
        check += n & 1 ^ n >> 1 & 1 ^ n >> 2 & 1 ^ n >> 3 & 1;
        check += n & 1 ^ n >> 1 & 1 ^ n >> 4 & 1 ^ n >> 5 & 1;
        check += n & 1 ^ n >> 2 & 1 ^ n >> 4 & 1 ^ n >> 6 & 1;
        int result = Integer.valueOf(check, 2);
        if (result != 0) {
            s[result - 1] = (s[result - 1] == '0')
                ? '1'
                : '0';
        }
    }
    public String getData() {
        return s[2] + "" + s[4] + "" + s[5] + "" + s[6];
    }
}