Несмежная форма ( НВС ) ряда является уникальным знаково-значным представлением , в котором ненулевые значения не могут быть смежными. Например:
- (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 обеспечивает уникальное представление целого числа , но его главное преимущество состоит в том, что вес Хэмминга для значения будет минимальным. Для обычных двоичных представлений значений половина всех битов в среднем будет отличаться от нуля, но с NAF это уменьшается до одной трети всех цифр.
Очевидно, что не более половины цифр не равны нулю, поэтому он был введен GW Reitweisner [1] для ускорения алгоритмов раннего умножения, во многом как кодирование Бута .
Поскольку каждая ненулевая цифра должна быть смежной с двумя нулями, представление NAF может быть реализовано таким образом, чтобы оно занимало максимум m + 1 бит для значения, которое обычно было бы представлено в двоичном формате с m битами.
Свойства NAF делают его полезным в различных алгоритмах, особенно в некоторых в криптографии ; например, для уменьшения количества умножений, необходимых для выполнения возведения в степень . В алгоритме возведения в степень возведением в квадрат количество умножений зависит от количества ненулевых битов. Если показатель здесь задан в форме NAF, цифровое значение 1 подразумевает умножение на основание, а цифровое значение -1 на его обратное.
Другие способы кодирования целых чисел, которые избегают последовательных единиц, включают кодирование Бута и кодирование Фибоначчи .
Преобразование в NAF
Существует несколько алгоритмов получения NAF-представления значения, заданного в двоичном формате. Одним из таких способов является следующий метод с повторным делением; он работает, выбирая ненулевые коэффициенты, так что результирующее частное делится на 2 и, следовательно, следующий коэффициент равен нулю. [2]
Вход E = ( e m −1 e m −2 ··· e 1 e 0 ) 2 Выход Z = ( z m z m −1 ··· z 1 z 0 ) NAF i ← 0 а E > 0 делаем если E нечетное, то z i ← 2 - ( E mod 4) E ← E - z i еще z i ← 0 E ← E / 2 i ← i + 1 вернуть z