[아홉가지 알고리즘] 05. 오류 정정코드

미래를 바꾼 아홉가지 알고리즘 - 존 맥코믹

오류 정정 코드

 1. 오류 정정 코드의 필요성... 이라는 걸 설명할 필요가 있나? 기껏 오늘 하루종일 작업한게 오류나서 잘못 세이브가 되면? 혹은 제대로 세이브 했어도 잘못 로드해왔다면? ...... 

이 오류를 검출/정정하기 위한 몇가지 트릭이 존재함

2. 반복 트릭

- 많이 보내면 원래 보내려던 값을 쉽게 알아낼 수 있다.

- 예를 들어 4491 을 전송하고자 한다면 아래와 같은 결과값이 나올 수 있다. 물론 통신상태는 당연히 엉망이다.

1 : 4491

2 : 4393

3 : 2491

4 : 4901

5 : 1991

---

각 자리수마다, 가장 많이 전송된 숫자를 조합하면 44.91 이 됨.

하지만 이건 너무 비효율적이다. 물론 신뢰하지 못할 만한 데이터를 1000번 정도 다시 받으면 신뢰할 만한 데이터가 뽑혀지기야 하겠지만, 저건 고작 4개의 숫자인데도 4000번을 보내야 하는데, 막.... 롤챔 방송을 본다고 치자. 미친 짓 아니겠는가? 

3. 리던던시 트릭

그래서 좀 나은 방법이 ㄴ있다. 이 신뢰하지 못할 만한 데이터를 신뢰할 수 있게 만들기 위해서는 잉여 정보...를 보내야 한다.

아까 보내려던 4491 을, 리던던시 트릭에 맞게 다시 보내보자. 물론 아까처럼 통신상태는 엉망.

1 : pour fuur niwe onq

읽어볼 수 있..지 않을까 ? four, four, nine, one

이 4491 을 four, four, nine, one 으로 바꾸는 게 인코딩! 이고 전송된 저 pour fuur niwe onq 을 4491 로 바꾸는게 디코딩! 이다.

컴퓨터과학자들은 '오버헤드'라는 맥락에서 오류 정정 시스템에 대한 비용을 측정.

여기서 말하는 오버헤드는... 뭐 본래의 뜻과 마찬가지긴 하지만.. '더 보내야 하는 잉여 정보의 양' 정도로 이해하면 될 듯. 잉여 정보..라는 단어는 리던던시 트릭에서만 썼지만 사실상 반복 트릭에서의 데이터 사본 역시 잉여 정보의 일종이다.

리던던시 트릭 역시 오버헤드가 적은 편은 아니지만 반복트릭보다 훨씬 오버헤드가 적고 성능 면에서도 보다 뛰어나기 때문에 리던던시 트릭을, 반복트릭보다 더 선호한다.

4. 체크섬 트릭

사실 오류는 '정정'보다는 '검출'에 더 중점을 둬야한다. 정정은 사실 안 해도 된다. 다시 데이터를 요청하면 되기 때문이지. 리던던시 트릭에서는 잉여 정보로부터 데이터를 산출하기 때문에 검출과 동시에 정정이 되긴 하지만... 사실 굳이!!!! 정정해줄 필요 까지는 없다.

오류를 검출하고, 만약 오류가 있다면 데이터 재전송을 요청하는 것을 체크섬 트릭이라고 한다.체크섬 트릭에도 뭐... 검출하는 방법이야 사실 비슷한데, 먼저 개념 자체를 설명하기 위해서.. 데이터가 오로지 숫자로만 되어있다고 가정하자.

- 단순 체크섬 트릭

아까 보내려던 4491 를 체크섬 트릭을 통해서 보자. 4 + 4 + 9 + 1 = 18... 본의 아니게 이런 숫자가 나왔군. 이 데이터의 단순 체크섬은 '8' 이다. 그런데 만약에 숫자 여러개가 잘못 전송된다면? 

5391 의 단순 체크섬 역시 8 인데? .... 

- 그래서 나온 계단 체크섬

(4 * 1) + (4 * 2) + (9 * 3) + (1 * 4) = 4 + 8 + 27 + 4 = 44 ...? 인가... 그러면 이제 이 4491의 계단 체크섬은 4!!

요건 아무리 꼬아서 전송해봤자... 체크섬 값이 같아지기 힘들다. 체크섬 값은 맨 마지막 값.

1원본 메세지         : 4 4 9 1 4

2하나 잘못됨         : 4 4 1 1 9

3두개 잘못됨         : 4 4 0 7 0

4두개 잘못됨         : 6 4 7 1 9

물론 실제 체크섬은 이렇게 간단하진 않음 ' '

핀포인트 트릭.... 이 남긴 했는데 요건 다음시간에... 졸립당.