// 피보나치 부호화 - 황금비 수학에 기반한 자기 동기화 코드
추가 매개변수 없이 모든 양의 정수에 대해 동작합니다.
11 패턴을 이용해 전송 오류 이후에도 동기화를 복구할 수 있습니다.
피보나치 수열과 제켄도르프 정리에 기반합니다.
피보나치 부호화는 제켄도르프 정리를 사용합니다. 모든 양의 정수는 서로 인접하지 않은 피보나치 수들의 합으로 유일하게 표현될 수 있습니다. 코드는 이 표현을 2진수로 나타낸 것으로, 사용되는 피보나치 수 위치는 1, 사용되지 않는 위치는 0이며, 끝에 1 비트를 하나 더 붙여 종료를 표시합니다. 11 패턴은 코드어의 끝에서만 나타납니다.
피보나치 수열: 1, 2, 3, 5, 8, 13, 21... 1 = F(1) → 11 2 = F(2) → 011 3 = F(3) → 0011 4 = F(3)+F(1) → 1011 5 = F(4) → 00011 12 = F(5)+F(3)+F(1) → 101011 인접한 피보나치 수는 사용하지 않습니다 11 패턴은 코드 끝에서만 나타납니다
피보나치 부호화는 피보나치 수열을 사용하여 양의 정수를 표현하는 범용 코드입니다. 제켄도르프 정리에 기반하며, 11 패턴이 종료 지점에만 나타나는 자기 동기화 코드를 생성합니다.
제켄도르프 정리는 모든 양의 정수가 서로 인접하지 않은 피보나치 수들의 합으로 유일하게 표현될 수 있다고 말합니다. 이 표현이 피보나치 부호화의 기반이 됩니다.
두 개의 연속된 1 비트인 11 패턴은 각 코드어의 끝에만 나타납니다. 따라서 전송 중 오류가 발생한 후에도 디코더는 11을 찾아 코드어의 경계를 다시 찾을 수 있습니다.
피보나치 부호화는 데이터 압축 연구, 오류에 강한 전송 시스템, 이론 컴퓨터 과학 등에서 사용됩니다. 실용적인 효율성보다는 수학적 성질 때문에 더 많이 연구됩니다.