피보나치 부호화

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2013년 1월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

시리즈의 일부
숫자 체계
자리수 표기법 힌두-아랍 숫자 서부 아랍어 동아랍어 벵골어 데바나가리 구자라티 구르무키 오디아 신할라 타밀어 말레이람 텔루구 칸나다 종카 티베트어 발리어 버마어 자바어 크메르어 라오스 몽골어 순다어 태국어 동아시아 제도 컨템포러리 중국인 쑤저우 호킨 일본인입니다 한국인입니다 베트남의 이력 계수봉 탕구트 기타 시스템 역사 고대 에게 해 바빌로니아인 포스트클래식 시토시안 마야어 무이스카 5진수 퀴푸 루미 컨템포러리 체로키 카토비크 (이누피아크) 기수/베이스별 공통 전파/베이스 2 3 4 5 6 8 10 12 16 20 60 (표) 비표준 방사/베이스 바이젝트 (1) 부호 있는 자리수(균형 3진수) 혼합(요인) 아니요. 복합(2i) 비정수()) 비대칭
부호값 표기법 알파벳이 아닌 것 다락방 브라흐미 추바시 이집트어 에트루리아어 카로스티 선사 시대 계수 쐐기모양조어 로마인 집계 마크 알파벳 아브자드 아르메니아어 아랴바차 키릴 문자 ge4ez 그루지야어 글래골틱 그리스어 히브리어
숫자 체계 목록
v t

수학과 컴퓨팅에서 피보나치 부호화는 양의 정수를 이진 코드 워드로 인코딩하는 범용^{[citation needed]} 코드입니다.이것은 피보나치 수를 기반으로 한 정수의 표현 중 하나입니다.각 코드 워드는 "11"로 끝나며, 종료 전에 "11"의 다른 인스턴스는 포함되지 않습니다.

피보나치 코드는 Zeckendorf의 정리를 사용하는 위치 숫자 체계인 Zeckendorf 표현과 밀접하게 관련되어 있으며, 어떤 숫자도 연속된 1을 갖는 표현을 가지지 않는다는 특성을 가지고 있습니다.특정 정수에 대한 피보나치 코드 워드는 정확히 정수의 Zeckendorf 표현이며, 숫자의 순서가 뒤바뀌고 끝에 "1"이 추가됩니다.

정의.

$숫자{\displaystyle }$N${\displaystyle (\backslash }$$displaystyle$ N$\backslash !)$에 대해${\displaystyle }$d $0$) ,${\displaystyle \mathrm{d}}$ (${\displaystyle }$1 )${\displaystyle }$,${\displaystyle d}$(${\displaystyle k}$-${\displaystyle 1}$) ,$d ( 1$) , \$ldots , d$ ( $k-1 , d$ ( k )\ !$$}가$$N을 $나타내는$ 코드 워드의 자릿수를 $나타내면{\displaystyle }$ 다음과 같습니다.

${\displaystyle N=\sum _{i=0}^k-1}d(i)F(i+2), {\text{ 및 }}d(k-1)=d(k)=1.\!}$

여기서 F(i)는 ih 피보나치 번호입니다.따라서 F(i+2)는${\displaystyle }$1,${\displaystyle 2}$,${\displaystyle 3}$,${\displaystyle 5}$,${\displaystyle }$8, ${\displaystyle 13}$으로 $시작$하는 ih 고유 피보나치 번호입니다$.{$ $displaystyle$$$1, 2,$3, 5, 13,$ \$ldots$ $마지막{\displaystyle }$ 비트 d$(k)$는 항상 1비트를 포함하지 않습니다.

이러한 부호화는 고유하며, 코드 워드에서 "11"의 유일한 발생은 d(k-1)와 d(k)의 끝이라는 것을 알 수 있다.두 번째 비트는 최상위 비트이고 첫 번째 비트는 최하위 비트입니다.또한 선행 0은 10진수처럼 생략할 수 없습니다.

첫 번째 몇 개의 피보나치 코드와 피보나치 코드 중 최소 크기의 코드를 가진 각 번호의 값인 이른바 암묵적 확률을 다음에 나타냅니다.

기호.	피보나치 표현	피보나치 코드워드	암묵적
1	${\displaystyle F(2)}$	11	1/4
2	${\displaystyle F(3)}$	011	1/8
3	${\displaystyle F(4)}$	0011	1/16
4	${\displaystyle F(2)+F(4)}$	1011	1/16
5	${\displaystyle F(5)}$	00011	1/32
6	${\displaystyle F(2)+F(5)}$	10011	1/32
7	${\displaystyle F(3)+F(5)}$	01011	1/32
8	${\displaystyle F(6)}$	000011	1/64
9	${\displaystyle F(2)+F(6)}$	100011	1/64
10	${\displaystyle F(3)+F(6)}$	010011	1/64
11	${\displaystyle F(4)+F(6)}$	001011	1/64
12	${\displaystyle F(2)+F(4)+F(6)}$	101011	1/64
13	${\displaystyle F(7)}$	0000011	1/128
14	${\displaystyle F(2)+F(7)}$	1000011	1/128

정수 N을 인코딩하려면:

1. N 이하의 가장 큰 피보나치 수를 구합니다.나머지 수를 추적하면서 N에서 이 수를 뺍니다.
2. 감산된 숫자가 ih Fibonacci 번호 F(i)일 경우 코드 워드에 i-2 자리에 1을 배치합니다(왼쪽 끝자리는 0 자리).
3. 나머지 0 에 도달할 때까지, 나머지를 N 으로 치환하고, 앞의 순서를 반복합니다.
4. 코드 워드의 맨 오른쪽 자리 뒤에 1을 추가합니다.

코드 워드를 디코딩하려면 마지막 "1"을 제거하고 나머지 값 1,2,3,5,8,13을 할당합니다...(Fibonacci 숫자)를 코드 워드의 비트로 전송하고 "1" 비트의 값을 합산합니다.

다른 범용 코드와의 비교

피보나치 코딩에는 다른 범용 코드와 비교하여 매력적인 특성이 있습니다.이는 자기 동기화 코드의 일례이며 손상된 스트림에서 데이터를 쉽게 복구할 수 있습니다.대부분의 다른 범용 코드에서는 단일 비트가 변경되면 해당 비트 뒤에 오는 데이터는 올바르게 읽히지 않습니다.한편, Fibonacci 코딩에서는 비트가 변경되면 1개의 토큰이 2개로 읽히거나 2개의 토큰이 1개로 잘못 읽히기도 하지만 스트림에서 "0"을 읽으면 오류가 더 이상 전파되지 않습니다."0"이 없는 스트림은 "11" 토큰 스트림뿐이므로 단일 비트 오류로 손상된 스트림과 원래 스트림 간의 편집 거리는 최대 3입니다.

이 접근법 - 일부 패턴(예: "11")이 금지된 기호 시퀀스를 사용하여 인코딩하는 방법은 자유롭게 ^[1]일반화할 수 있습니다.

예

다음 표는 65 = 2 + 8 + 55이므로 숫자 65가 0100100011로 피보나치 코딩으로 표현된 것을 보여줍니다.처음 두 개의 피보나치 번호(0 및 1)는 사용되지 않으며 항상 추가 1이 추가됩니다.

${\displaystyle{\begin{배열}{ccccccccccc c}\hline 0&, 1&, 1&, 2&, 3&, 5&, 8&, 13&, 21&, 34&, 55&,-\\\hline F(0)&, F(1)&, F(2)&, F(3)&, F(4)&, F(5)&, F(6)&, F(7)&, F(8)&, F(9)&, F(10)&,\scriptstyle{\text{추가}}\\\hline -&, -&, 0&, 1&, 0&, 0&, 1&, 0&, 0&, 0&, 1&,1\\\hline \e.nd{배열}}}$

일반화

양의 정수에 대한 피보나치 인코딩은 "11"로 끝나는 이진 문자열이며 "11"의 다른 인스턴스를 포함하지 않습니다.이는 N개의 연속 1로 끝나는 이진 문자열로 일반화할 수 있으며 N개의 연속 1의 다른 인스턴스를 포함하지 않습니다.예를 들어 N = 3의 경우 양의 정수는 111, 0111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …로 인코딩됩니다.이 경우 문자열 길이의 함수로서의 부호화 수는 Trivonacci 번호의 시퀀스에 의해 지정됩니다.

주어진 기호 뒤에 허용되는 기호를 정의하는 일반적인 제약조건의 경우, 최대 정보 속도는 먼저 최대 엔트로피 랜덤 워크를 사용하여 최적의 전이 확률을 찾은 다음 엔트로피 코더를 사용하여 메시지를 찾은 최적 t를 충족하는 일련의 기호로 인코딩함으로써 얻을 수 있다.몸값 확률

「 」를 참조해 주세요.

• 황금비율기준
• NegaFibonacci 부호화
• 오스트로프스키 수
• 유니버설 코드
• Varicode, 실용적인 응용 프로그램
• 체켄도르프의 정리
• 최대 엔트로피 랜덤 워크

레퍼런스

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 105. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Robust universal complete codes for transmission and compression". Discrete Applied Mathematics. 64 (1): 31–55. CiteSeerX 10.1.1.37.3064. doi:10.1016/0166-218X(93)00116-H. ISSN 0166-218X. Zbl 0874.94026.

추가 정보

• Stakhov, A. P. (2009). The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science. Singapore: World Scientific Publishing.