소스 부호화

문제를 푸는 것으로 시작해 봅시다 앨리스와 밥은 서로 보이지 않을 정도로 멀리 떨어져 있는 나무 요새에 삽니다 그리고 그들은 서로 소통을 해야합니다 그래서 둘은 둘의 집 사이에 줄을 하나 달기로 결정합니다 줄을 팽팽하게 당기고 각각의 끝에 빈깡통을 달아둡니다 목소리를 어렴풋이 전달해줄 수 있도록 하기 위함이죠 하지만 여기에는 문제가 있습니다 잡음이죠 언제든지 강한 바람이 불 수 있고 이는 잡음 너머로 신호를 듣는 것이 불가능하게 합니다 그러므로 신호의 에너지 강도를 크게할 방법과 이를 잡음과 분리할 방법이 필요합니다 이것은 밥의 아이디어입니다 간단하게 줄을 튕겨 잡음 속에서도 신호를 쉽게 찾을 수 있도록 할 수 있습니다 그러나 이 아이디어는 새로운 문제를 가져옵니다 어떻게 하면 메시지를 튕김으로 부호화 할 수 있을까요? 이 둘이 거리가 먼 상태에서 보드게임을 하고 싶다고 합시다 처음에는 대부분 간단한 메시지로 대결할 것입니다 그들이 보낼 메시지가 될 두개의 주사위를 굴린 결과는 11가지의 한정적인 가능한 숫자들의 경우 중에서 선택될 것으로 생각할 수 있고 이를 이산 정보원이라고 합니다 처음에는 간단한 방법을 사용하기로 정했습니다 줄을 튕기는 숫자를 이용하여 결과를 보낼 것입니다 그러므로 3이라는 결과를 위해서 그들은 세번 줄을 튕길 것입니다 9라면 아홉 번 12라면 열두 번을 튕길 것입니다 하지만 둘은 곧 이것이 필요보다 더 오래 걸린다는 것을 발견했습니다 연습을 통해 아무리 빠르더라도 1초에 2번 튕기는 것이 최고로 빠른 것이라는 것을 알았고 더 빨라지면 헷갈렸습니다 그러므로 1초에 두번 튕기는 것이 이 방법으로 신호를 전달하기 위한 수용력이나 비율로 생각될 수 있습니다 가장 잘 나오는 숫자는 7이었고 이 숫자를 전달하기 위해서 3.5초라는 시간이 필요합니다 Alice는 부호화 방법을 바꾼다면 보다 나은 작업을 할 수 있음을 깨달았습니다 각 숫자의 확률은 간단한 패턴을 따랐습니다 굴려서 2가 나올 방법이 하나 굴려서 3이 나올 방법이 두가지 굴려서 4가 나올 방법이 세가지 굴려서 5가 나올 방법이 네가지 굴려서 6이 나올 방법이 다섯가지 굴려서 7이 나올 방법이 여섯가지 굴려서 8이 나올 방법이 다섯가지 굴려서 9이 나올 방법이 네가지 이런식으로 12가 나올 한가지 방법까지 있습니다 이 그래프는 각각의 경우의 수를 보여줍니다 그러면 이러한 패턴이 명백하게 보입니다 이걸 각 숫자를 몇 번 튕겨야하는지 나타내는 그래프로 바꾸어보죠 앨리스는 계속해서 가장 많이 나오는 숫자인 7을 가장 짧은 신호인 한번 튕기는 것으로 지정하였고 계속해서 두 번째로 가장 많이 나오는 숫자를 지정합니다 만일 같은 것이 있다면 무작위로 하나를 선택합니다 이 경우엔 6이라면 두번 튕기고 8이면 세 번 튕기기로 정했습니다 그러한 방식으로 5는 네 번 튕기고 9는 다섯 번을 튕깁니다 이런식으로 12가 나오면 열한 번을 튕기기로 할 때까지 계속합니다 이제 가장 많이 나오는 숫자인 7을 1초도 안되는 시간에 보낼 수 있습니다 어마어마한 발전입니다 이러한 기호의 변환법은 평균적으로 동일한 시간안에 보다 많은 정보를 보낼 수 있게 해줍니다 사실 이러한 코딩 방법은 이 예제에선 최적화되어 주사위를 굴린 결과를 동일한 튕김을 사용해 보낸다면 더 빠른 방법은 없습니다 그러나 몇번 줄을 튕긴후에 밥에게 새로운 아이디어가 떠올랐습니다