Сандарды бейнелеудің қанағаттандырылған цифрлық форматы (NAF) туралы. Бірегей, минималды салмақты және тиімді өрнеуді ұсынады. SEO үшін оптимизацияланған.
Бәрі 7 санының дұрыс қолтаңбалы цифрлық бейнелеуі, бірақ тек соңғы бейнелеу (1 0 0 −1) ғана жанындас емес түрде. Жанындас емес түр "канондық қолтаңбалы цифр" бейнелеуі деп те аталады.
All are valid signed digit representations of 7, but only the final representation, (1 0 0 −1), is in non adjacent form. The non adjacent form is also known as "canonical signed digit" representation.
Қасиеттері
NAF бүтін санның бірегей бейнелеуін қамтамасыз етеді, бірақ оның басты артықшылығы – мәннің Хамминг салмағы ең төменгі мәнге ие болуы. Мәндердің стандартты екілік бейнелеулері үшін, орташа есеп бойынша, барлық биттердің жартысы нөлдік емес болады, бірақ NAF қолданғанда бұл көрсеткіш барлық цифрлардың үштен біріне дейін төмендейді. Бұл аппараттық цифрлық сигналдарды өңдеуде қосу/алу желілерін (мысалы, константаға көбейту) тиімді жүзеге асыруға мүмкіндік береді. Әрине, цифрлардың көп дегенде жартысы нөлдік емес, осы себепті Г. В. Райтвейснер оны Бут кодтау сияқты ерте көбейту алгоритмдерін жылдамдату үшін енгізді. Кез келген нөлдік емес цифр екі 0-ге іргелес болуы керек болғандықтан, NAF бейнелеуін жүзеге асыру үшін, әдетте m битпен екілік түрінде бейнеленетін мән үшін тек m + 1 бит қана қажет болады. NAF-тың қасиеттері оны әртүрлі алгоритмдерде, әсіресе криптографиядағы кейбір алгоритмдерде пайдалы етеді; мысалы, экспоненталауды есептеу үшін қажетті көбейтулер санын азайту үшін. Экспоненталауды квадраттау алгоритмінде көбейтулер саны нөлдік емес биттер санына байланысты. Егер экспонента NAF түрінде берілген болса, 1 цифрлік мәні негізге көбейтуді, ал -1 цифрлік мәні оның кері көбейтуін білдіреді. Бірінен соң бірі келетін 1-ді болдырмау үшін бүтін сандарды кодтаудың басқа әдістеріне Бут кодтау және Фибоначчи кодтау жатады.
NAF assures a unique representation of an integer, but the main benefit of it is that the Hamming weight of the value will be minimal. For regular binary representations of values, half of all bits will be non zero, on average, but with NAF this drops to only one third of all digits. This leads to efficient implementations of add/subtract networks (e. g. multiplication by a constant) in hardwired digital signal processing. Obviously, at most half of the digits are non zero, which was the reason it was introduced by G. W. Reitweisner for speeding up early multiplication algorithms, much like Booth encoding. Because every non zero digit has to be adjacent to two 0s, the NAF representation can be implemented such that it only takes a maximum of m + 1 bits for a value that would normally be represented in binary with m bits. The properties of NAF make it useful in various algorithms, especially some in cryptography; e. g., for reducing the number of multiplications needed for performing an exponentiation. In the algorithm, exponentiation by squaring, the number of multiplications depends on the number of non zero bits. If the exponent here is given in NAF form, a digit value 1 implies a multiplication by the base, and a digit value −1 by its reciprocal. Other ways of encoding integers that avoid consecutive 1s include Booth encoding and Fibonacci coding.