[알고리즘] Hamming Code 구현

데이터에서가장낮은자리의비트의위치를1로정하고, 자리가한자리씩높아질수록그위치를2, 3, 4, ...으로부여한다.

 

1. 데이터에서2의거듭제곱이되는위치(예를들어, 1, 2, 4, 8, 16, 32, 64 등)의비트는모두패리티비트로사용된다.

2. 다른모든위치의비트는실제데이터를위하여사용된다.

3. 각위치의패리티비트는해밍코드의특정위치에있는비트들의패리티를나타낸다. 위치가1, 2, 4, 8, 16 등에있는패리티비트를P1, P2, P4, P8, P16등으로나타낼때, 이패리티비트가검사하는비트의위치는다음과같다(아래그림참조).

 

3.1. P1: 위치가1인비트에서시작하여, 한비트를검사하고, 한비트를건너뛰고, 한비트를검사하고, 한비트를건너뛰어검사하는것을반복한다. 단,위치가1인비트(P1자신)는검사하지않는다.

3.2. P2: 위치가2인비트에서시작하여, 두비트를검사하고, 두비트를건너뛰고, 두비트를검사하고, 두비트를건너뛰어검사하는것을반복한다. 단,위치가2인비트(P2자신)는검사하지않는다.

3.3. P4: 위치가4인비트에서시작하여, 네비트를검사하고, 네비트를건너뛰고, 네비트를검사하고, 네비트를건너뛰어검사하는것을반복한다. 단,위치가4인비트(P4자신)는검사하지않는다.

3.4 .P8: 위치가8인비트에서시작하여, 여덟비트를검사하고, 여덟비트를건너뛰고, 여덟비트를검사하고, 여덟비트를건너뛰어검사하는것을반복한다. 단,위치가8인비트(P8자신)는검사하지않는다.

3.5. P16: 위치가16인비트에서시작하여, 열여섯비트를검사하고, 열여섯비트를건너뛰고, 열여섯비트를검사하고, 열여섯비트를건너뛰어검사하는것을반복한다. 단, 위치가16인비트(P16자신)는검사하지않는다.

3.6. 다른위치에있는패리티비트들도이와같은방법으로패리티를계산한다.

 

#include<iostream>
using namespace std;

int main(){
	int k=0x00;
	unsigned int out=0x00;
	unsigned int num=0x00;
	cin>>k>>num;
	int arr1[32]={0x00,};
	if(k==0){
		num=((num<<5)&0xffff0000)|((num<<4)&0x00007f00)|((num<<3)&0x00000070)|((num<<2)&0x00000004);
		for(int i=0;i<32;i++) arr1[31-i]=(num>>i)&0x01;
		
		
		int count=0x00;
		//p1
		count=0;
		for(int i=1;i<30;i+=2){
			if(arr1[i]==1) count++;
		}
		if(count%2!=0) arr1[31]=1;

		//p2
		count=0;
		for(int i=1;i<30;i+=3){
			if(arr1[i++]==1) count++;
			if(arr1[i]==1) count++;
		}
		if(count%2!=0) arr1[30]=1;

		//p4
		count=0;
		for(int i=0;i<4;i++){
			if(arr1[i+1]==1) count++;
			if(arr1[i+9]==1) count++;
			if(arr1[i+17]==1) count++;
			if(arr1[i+25]==1) count++;
		}
		if(count%2!=0) arr1[28]=1;

		//p8
		count=0;
		for(int i=1;i<=8;i++){
			if(arr1[i]==1) count++;
			if(arr1[i+16]==1) count++;
		}
		if(count%2!=0) arr1[24]=1;

		//p16
		count=0;
		for(int i=1;i<=16;i++){
			if(arr1[i]==1) count++;

		}
	    if(count%2!=0) arr1[16]=1;
		
		for(int i=0;i<32;i++){
			out|=(arr1[i]<<(31-i));
		}

	}

	else if(k==1){
		for(int i=0;i<32;i++) arr1[31-i]=(num>>i)&0x01;
		int count[5]={0x00,};
		//p1
		for(int i=1;i<32;i+=2){
			if(arr1[i]==1) count[0]+=1;
		}
		if(count[0]%2!=0) count[0]=1;
		else count[0]=0;

		//p2
		for(int i=1;i<31;i+=3){
			if(arr1[i++]==1) count[1]++;
			if(arr1[i]==1) count[1]++;
		}
	    if(count[1]%2!=0) count[1]=2;
		else count[1]=0;

		//p4
		for(int i=0;i<4;i++){
			if(arr1[i+1]==1) count[2]++;
			if(arr1[i+9]==1) count[2]++;
			if(arr1[i+17]==1) count[2]++;
			if(arr1[i+25]==1) count[2]++;
		}
	    if(count[2]%2!=0) count[2]=4;
		else count[2]=0;

		//p8
		for(int i=1;i<=8;i++){
			if(arr1[i]==1) count[3]++;
			if(arr1[i+16]==1) count[3]++;
		}
		if(count[3]%2!=0) count[3]=8;
		else count[3]=0;

		//p16
		for(int i=1;i<=16;i++){
			if(arr1[i]==1) count[4]++;

		}
		if(count[4]%2!=0) count[4]=16;
		else count[4]=0;


		int pb=0;
		for(int i=0;i<5;i++){
			if(count[i]!=0) pb+=count[i];
		}

		if(pb!=0) {
			if(arr1[32-pb]==1) arr1[32-pb]=0;
			else if (arr1[32-pb]==0) arr1[32-pb]=1;
		}
		for(int i=0;i<32;i++){
			if(i==16||i==24||i==28||i==30||i==31) continue;
			else{
				out<<=1;
				out|=arr1[i];
			}
		}

	}
	

	
	
	cout<<out<<endl;
	
	


}