홀로그래피 오류 정정

[2024 간쓸개 시즌4 1주차 day3 첫번째 지문]

홀로 그래피를 저장할 때, 오류가 생기는 것을 고려하여 값을 '삼중 반복 부호화'처럼 반복해서 저장한다. 그러나 여기서는 단순 반복을 하진 않고, 변형을 한다. 순서를 생각해보면

'홀수열 확장 페이지'와 '짝수열 확장 페이지'를 만든다. 전자는 기존 홀수열을 각각 3개로 확장하고, 기존 짝수열을 모두 검은 칸으로  만들되, 기존 홀수열의 맨 처음은 2개로 확장하는 방식이다.

비슷하게 후자는 기존 짝수열을 각각 3개로 확장하고, 기존 홀수열을 모두 검은 칸으로 만들되, 기존 짝수열의 맨 마지막은 2개만 확장한다.예를 들어 0을 검은색, 2을 흰색이라고 했을 때, 0-2-2-0-2-0 에 대해 각각

{0-0}-0-{2-2-2}-0-{2-2-2}-0,

0-{2-2-2}-0-{0-0-0}-0-{0-0} 이 된다.

 이렇게 각 페이지를 만들고, 이를 이용하여 '결합 페이지'를 만든다. 각 위치에 대해 같은 색이라면 해당 색으로 서로 다른 색이라면 회색으로 설정하여 페이지를 만든다. 회색을 1라고 할 때, 0-2-2-0-2-0에 대한 결합 페이지는 

0-1-1-2-1-1-0-1-1-1-0 가 된다. 내가 설정할 숫자로는 단순히 각 위치에 대해 평균을 구하면 된다.

만들어진 결합 페이지에 대해 세자리씩 구분할 수 있다. 그 세자리의 묶음을 ㅁ이라고 하겠다. 처음 세 개를 하나로 묶어서 ㅁ을 만들고, 거기의 마지막 칸은 다시 다음 ㅁ을 만드는 첫번째 칸이 된다. 

그렇게 ㅁ을 만들었을 때, '검검검' '회회검' '검회회' '회흰회'의 경우 즉 '000' '110' '011' '121'만 가능하기 때문에 오류를 수정할 수 있다. 예를 들어 0-1-1-2-1-1-0-1-1-1-0에서 만드는 ㅁ의 조합은

0-1-1

1-2-1

1-1-0

0-1-1

1-1-0

뿐이다.

따라서 0-X-1-2-1-1-0-X-1-1-0이런 식으로 오류가 났을 때, 둘 다 1임을 알 수 있다.

그렇게 정정한 후, 홀수열의 데이터만 읽되 검은색은 검은색, 회색은 흰색으로 읽으면 원래의 페이지에 담긴 데이터를 얻을 수 있다. 0-1-1-2-1-1-0-1-1-1-0여기에선 0-1-1-0-1-0이니 0-2-2-0-2-0이 된다. 단순히 홀수열의 데이터가 양수인지 0인지만 판단하면 된다. 

 

질문!!!

 

일단 개수의 차이가 있다. 원문을 2N이라고 할 때, '삼중 반복 부호화'는 길이가 6N이 되지만, 이 방식의 경우에는  4N-1이 된다. 이런 점에서는 더 좋다고 할 수 있을 것이다. 물론 단점도 있는 거 같다. 계산과정이 그렇게 간단해 보이진 않는다.

데이터를 $a _1-a_2-a_3-\dots-a_{2n-1}-a_{2n}$이라고 했을 때, 확장페이지는 각각

$a_1-a_1-0-a_3-a_3-a_3-0-a_5-a_5-a_5-\dots-a_{2n-1}-a_{2n-1}-a_{2n-1}-0$

$0-a_2-a_2-a_2-0-a_4-a_4-a_4-0-a_6-\dots-a_{2n-2}-0-a_{2n}-a_{2n}$

이 되기 때문에 결론적으로 결합 페이지는

$(a_1,0)-(a_1,a_2)-(0,a_2)-(a_3,a_2)-(a_3,0)-(a_3,a_4)-(0,a_4)-(a_5,a_4)-\dots-(a_{2n-1},0)-(a_{2n-1},a_{2n})-(0,a_{2n})$

로 만들어진다. (,)는 일단 함수로써 생각하면 된다.

$(a_x,0)-(a_x,a_{x+1})-(0,a_{x+1})$의 조합만이 가능할 수 밖에 없다.

{0이 무조건 포함된 조합}-{연속된 두개로 이루어진 조합}-{0이 무조건 포함된 조합} 이런 식일 수 밖에 없다.

여기서 총 4가지의 경우인 '000' '011' '110' '121'가 가능하다는 것을 알 수 있다. 

삼중 반복 부호화는 3개로 확장된 데이터중 2개에 오류가 생기면 올바른 정정을 할 수 없다. 이와 비슷하게 ㅁ조합을 만들 때, 항상은 아니지만 3개 중 2개의 오류가 발생했을 때, 남은 숫자가 2가 아니라면 복구가 불가능하고, 2라면 가능하다.

결합 페이지의 홀수열을 모으면 항상

$(a_1,0)-(a_2,0)-(a_3,0)-(a_4,0)-\dots$가 될 수 밖에 없다. (,)함수는 둘다 0일 때만 0이 되므로 0인지 양수인지만 판단하면 된다.