비인접형식

Non-adjacent form
숫자 시스템
힌두-아랍어 수 체계
동아시아인
미국인의
알파벳
이전
베이스별 위치 시스템
비표준 위치수 시스템
숫자 체계 목록

숫자의 비인접 형태(NAF)는 0이 아닌 값이 인접할 수 없는 고유한 서명 자리 표시다.예를 들면 다음과 같다.

(0 1 1 1)2 = 4 + 2 + 1 = 7
(1 0 −1 1)2 = 8 − 2 + 1 = 7
(1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7
(1 0 0 −1)2 = 8 − 1 = 7

모두 유효한 서명 자리 표시 7이지만 최종 표시(1 0 0 -1)만 비인접 형식으로 되어 있다.2

비인접 형태는 "캐논 서명된 숫자" 표현으로도 알려져 있다.

특성.

NAF는 정수의 고유한 표현을 보장하지만, 그 값의 해밍 중량은 최소화할 것이라는 것이 주된 장점이다.값의 정규 이항 표현에 대해, 모든 비트의 절반은 평균적으로 0이 아니지만, NAF를 사용하는 경우, 이것은 전체 숫자의 1/3만 감소한다.이는 유선 연결된 디지털 신호 처리에서 추가/추상 네트워크(예: 상수에 의한 곱하기)의 효율적인 구현으로 이어진다.[1]

분명히, 숫자의 거의 절반은 0이 아닌 숫자인데, 이것이 Booth 인코딩과 같이 초기 곱셈 알고리즘을 가속화하기 위해 G.W. Reitweisner에 의해 소개된 이유였다.

0이 아닌 모든 자릿수는 두 개의 0에 인접해야 하기 때문에 NAF 표현은 일반적으로 m 비트와 함께 이진수로 표현되는 값에 대해 최대 m + 1비트만 사용할 수 있도록 구현될 수 있다.

NAF의 속성은 다양한 알고리즘, 특히 암호학에서 유용하게 쓰인다. 예를 들어, 지수를 수행하는 데 필요한 승수의 수를 줄이는 데 사용된다.제곱에 의한 지수화 알고리즘에서 승수의 수는 0이 아닌 비트의 수에 따라 달라진다.여기서 지수를 NAF 형식으로 지정하면 숫자 값 1은 기준의 곱셈을 의미하며 숫자 값 -1은 역수를 의미한다.

연속 1초를 피하는 정수를 인코딩하는 다른 방법으로는 부스 인코딩과 피보나치 코딩이 있다.

NAF로 변환 중

이진수로 주어진 값의 NAF 표현을 얻기 위한 몇 가지 알고리즘이 있다.그러한 방법 중 하나는 반복적인 구분을 사용하는 다음과 같은 방법이다. 이는 결과 지수를 2로 나누어 다음 계수는 0으로 나누도록 0이 아닌 계수를 선택함으로써 작용한다.[3] 

입력 E = (em−1m−2 ···e101)2 출력 Z = (zmm−1 z ·· z0)NAF i ← 0, E > 0은 E가 홀수일 경우 zi ← 2 - (E mod 4) E - z 다른i zi ← E/2 i + 1 반환 z

Prodinger에[4] 의해 더 빠른 방법이 주어진다. 여기서 x는 입력이고, np는 양의 비트 문자열이고 nm는 음의 비트 문자열이다.

입력 x 출력 np, nm xh = x >> 1; x3 = x + xh; c = xh ^ x3; np = x3 & c; nm = xh & c;

예를 들어 A184616에서 사용된다.

외부 링크

  • 표준 서명 숫자 표현 소개
  • Fractions in the Canonical-Signed-Digit Number System. Conference on Information Sciences and Systems. The Johns Hopkins University. March 21–23, 2001. CiteSeerX 10.1.1.126.5477.

참조

  1. ^ Hewlitt, R.M. (2000). "Canonical signed digit representation for FIR digital filters". Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on: 416–426. doi:10.1109/SIPS.2000.886740. ISBN 978-0-7803-6488-2. S2CID 122082511.
  2. ^ George W. Reitwiesner, Binary Mathing, Advance in Computers, 1960.
  3. ^ D. 행커슨, A.메네즈와 S.A.Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004. 페이지 98.
  4. ^ Prodinger, Helmut. "On Binary Representations of Integers with Digits -1, 0, 1" (PDF). Integers. Retrieved 25 June 2021.