🎈영향력 있는 알고리즘 TIL#35

영향력 있는 알고리즘 중, 웹 검색 알고리즘에 이어 영향력 있는 알고리즘에 대해 알아보자!

오류 정정 알고리즘

• 계산 수행 : 데이터를 조작
• 데이터 저장 : 입력된 데이터를 저장
• 데이터 전송 : 데이터를 필요한 곳으로 전송한다. 데이터 전송에서 가장 중요한 것은 데이터를 정확하게 전송하는 것

데이터 전송 에러를 고치는 방법

오류 검출과 정정을 수행하는 방법
-반복 알고리즘 (가장 기본적)
-리던던시 알고리즘 : 패리티 검사 코드 사용

---

오류 검출에 집중하고, 에러를 발견했을 떄 재전송하는 방법
-체크섬 알고리즘, 계산 체크섬 알고리즘
-핀 포인트 알고리즘

컴퓨터에 사용하는 오류 정정 알고리즘의 종류

CD, DVD, 하드디스크 : 계산 체크섬 트릭과 핀 포인트 트릭을 결합하여 사용
인터넷 : 체크섬 트릭을 사용.

1. 반복 알고리즘

• 오류 검출 및 정정을 위한 가장 기본적인 방법

반복 알고리즘 사용하기
ex.

어떤 사람의 통장 잔고가 6,234,000원이다. 이것을 통신을 통해 다른 사람에게 보낸다고 생각해보자. 반복 알고리즘을 적용하기 위해 동일한 데이터를 5번 반복해서 보낸다.
전송1:623400
전송2:624400
전송3:523400
전송4:623400
전송5:623401
자료를 수신한 측에서 잔고가 얼마인지 알지 못한 채 다섯 번의 자료랄 받았다. 이 경우, 적용 할 수 있는 가장 좋은 방법은 각 항목별로 가장 빈도수가 높은 것을 선택하는 것 >> 최종 수신 값은 623400

---

반복알고리즘은 충분히 신뢰할 근거가 맞지만, 큰 자료를 다루기에는 부적합하다😅

2. 리던던시 알고리즘

• 통신의 오류를 발견하고 정정하기 위해, 보내는 데이터에 정보를 추가해서 보내는 방법
• 리던던시 알고리즘으로 제일 많이 사용되는 것은 해밍코드 알고리즘!

ex. 해밍코드 알고리즘 사용하기

(7,4) 해밍코드 사용하는 방법
4비트의 데이터를 보낸다고 가정하면 총 16개의 경우의 수가 발생(왜?..)
이떄, 각 경우에 대하여 오류 정정을 위한 3개의 비트를 추가해서 보내는 방법
0000 > 0000 000(기존코드에 000 추가)
0001 > 0001 011(기존코드에 011 추가)
0010 > 0010 111(기존코드에 111 추가)
0011 > 0011 100(기존코드에 100 추가)
이하 생략,,,
해밍코드에 의해 가장 부합되는 값을 찾을 수 있음! 리던던시 알고리즘은 7자리 코드에 있는 어떤 하나의 오류도 정확하게 찾아 낼 수 있도록 설계된 방법
> 이해가 가지 않는다,, 다시 공부해야지😂

3. 체크섬 알고리즘

보내는 데이터가 4,6,7,5,6 이라고 가정
데이터를 모두 합한다 : 4+6+7+5+6 = 28
합한 수의 마지막을 취한다 : 8(체크섬)
체크섬을 포함하여 보내야할 자료를 구성한다. 4,6,7,5,6,8
자료를 보낸다.
수신한 자료의 앞의 5자리를 더하고, 결과의 마지막 수가 8인지 확인한다.
8이면 데이터가 정확한 것, 아니면 재전송 요청

3-1) 계단 체크섬 알고리즘

• 체크섬이 2개의 에러를 가지면 체크섬이 같을 수 있으므로 체크섬 알고리즘을 보완하여 개발된 방법!

  보내는 데이터가 4,6,7,5,6 이라고 가정
  데이터를 그냥 합치지 않고 아래와 같이 진행
  : (1 x 4) + (2 x 6) + (3 x 7) + (4 x 5) + (5 x 6) = 87 (체크섬은 7)
  합한 수의 마지막을 취한다 : 7(체크섬)
  체크섬을 포함하여 보내야할 자료를 구성한다. 4,6,7,5,6,7
  자료를 보낸다.
  수신한 자료의 앞의 5자리를 대상으로 두 번쨰 과정을 수행.
  결과의 마지막 수가 7인지 확인
  7이면 데이터가 정확한 것, 아니면 재전송 요청

• 실무에서는 체크섬과 계단 체크섬을 동시에 사용하기도 함!!
  BUT! 체크섬은 큰 자료의 전송에는 사용하기 어려움 > 데이터를 보낼 때 수행하는 연산이 전체 시스템의 속도에 큰 영향을 주기 때문이다.

4. 핀 포인트 알고리즘

• 2차원 패리티라고 하며 복잡한 수학을 사용하지 않고, 오류를 찾고 정정하는 묘미를 가진 방법>> 다만, 비효율적이어서 많이 쓰지는 않는다.

  행과 열을 대상으로 체크섬을 만들고, 이것을 전체적으로 풀어서 전송
  수신된 데이터를 다시 조립한 후 체크섬 계산,,
  
  (이미지로 보면 쉬우나, 이미지를 벨로그에 그리기엔 너무 번거로우니 나중에 책을 참고하자, (알고리즘과 자료구조, p.151))