네가피보나치 부호화

수학에서, 네가피보나치 코딩은 0이 아닌 정수를 이진 코드 워드로 인코딩하는 보편적인 코드입니다.양의 정수와 음의 정수를 모두 나타낼 수 있다는 점을 제외하면 피보나치 부호화와 유사합니다.모든 코드는 "11"로 끝나며 종료 전에는 "11"이 없습니다.

인코딩 방법

0이 아닌 정수 X를 인코딩하려면:

홀수(또는 짝수) 네가피보나치 수를 1에서 N까지 합하여 N비트로 인코딩 가능한 가장 큰(또는 가장 작은) 숫자를 계산합니다.
N비트가 X를 포함하기에 충분하다고 판단되면 X에서 N번째 negafibonacci 숫자를 빼고 나머지를 추적한 다음 출력의 N번째 비트에 1을 넣습니다.
N번째 비트에서 첫 번째 비트로 아래쪽으로 작업하여 해당하는 각 네가피보나치 수를 나머지 수와 비교합니다.차이의 절대값이 더 작으면 나머지에서 빼고, 다음 상위 비트에 아직 차이 값이 없는 경우에는 나머지 값에서 뺍니다.감산이 이루어지면 1이 적절한 비트에 배치되고, 감산이 이루어지면 0이 됩니다.
N+1번째 비트에 하나를 넣으면 끝납니다.

코드에서 토큰을 디코딩하려면 마지막 "1"을 제거하고 나머지 비트에 값 1, -1, 2, -3, 5, -8, 13...을 할당합니다.(네가피보나치 숫자), "1" 비트를 추가합니다.

네가피보나치 표현

네가피보나치 코딩은 수학자들이 가끔 사용하는 위치 수 체계인 네가피보나치 표현과 밀접한 관련이 있습니다.특정 0이 아닌 정수에 대한 negafibonacci 코드는 자릿수가 반대로 되고 끝에 추가 "1"이 추가되는 것을 제외하고 정수의 negafibonacci 표현의 코드입니다.모든 음수에 대한 negafibonacci 코드는 홀수 자리수인 반면 모든 양수에 대한 negafi bonacci 코드는 짝수 자리수입니다.

테이블

-11부터 11까지의 정수 코드는 다음과 같습니다.

번호	네가피보나치 표현	네가피보나치 코드
−11	101000	0001011
−10	101001	1001011
−9	100010	0100011
−8	100000	0000011
−7	100001	1000011
−6	100100	0010011
−5	100101	1010011
−4	1010	01011
−3	1000	00011
−2	1001	10011
−1	10	011
0	0	(인코딩될 수 없음)
1	1	11
2	100	0011
3	101	1011
4	10010	010011
5	10000	000011
6	10001	100011
7	10100	001011
8	10101	101011
9	1001010	01010011
10	1001000	00010011
11	1001001	10010011

참고 항목

레퍼런스

인용된 작품

Knuth, Donald (2008). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting of the Mathematical Association of America. San Jose, California.
Knuth, Donald (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. ISBN 978-0-321-58050-4. 섹션 7.1.3의 출판 전 초안에서 특히 페이지 36–39를 참조합니다.
Margenstern, Maurice (2008). Cellular Automata in Hyperbolic Spaces. Advances in unconventional computing and cellular automata. Vol. 2. Archives contemporaines. p. 79. ISBN 9782914610834.

Search