Несмежная форма ( NAF ) числа — это уникальное знаковое цифровое представление , в котором ненулевые значения не могут быть смежными. Например:
Все они являются допустимыми знаковыми цифровыми представлениями числа 7, но только последнее представление, (1 0 0 −1) 2 , находится в несмежной форме.
Несмежная форма также известна как представление «канонической знаковой цифры».
NAF гарантирует уникальное представление целого числа , но его главное преимущество в том, что вес Хэмминга значения будет минимальным. Для обычных двоичных представлений значений в среднем половина всех битов будет ненулевой, но с NAF это число уменьшается до одной трети всех цифр. Это приводит к эффективным реализациям сетей сложения/вычитания (например, умножения на константу) в аппаратной цифровой обработке сигналов . [1]
Очевидно, что не более половины цифр не равны нулю, поэтому этот метод был введен Г. В. Рейтвайснером [2] для ускорения ранних алгоритмов умножения, во многом похожих на кодирование Бута .
Поскольку каждая ненулевая цифра должна быть смежной с двумя нулями, представление NAF может быть реализовано таким образом, что для значения, которое обычно представляется в двоичном виде с помощью m бит, потребуется максимум m + 1 бит .
Свойства NAF делают его полезным в различных алгоритмах, особенно в некоторых в криптографии ; например, для сокращения количества умножений, необходимых для выполнения возведения в степень . В алгоритме возведения в степень путем возведения в квадрат количество умножений зависит от количества ненулевых битов. Если показатель степени здесь задан в форме NAF, цифровое значение 1 подразумевает умножение на основание, а цифровое значение −1 — на его обратную величину.
Другие способы кодирования целых чисел, которые избегают последовательных единиц, включают кодирование Бута и кодирование Фибоначчи .
Существует несколько алгоритмов для получения представления NAF значения, заданного в двоичном формате. Одним из таких является следующий метод, использующий повторное деление; он работает путем выбора ненулевых коэффициентов таким образом, чтобы полученное частное делилось на 2, а следовательно, следующий коэффициент был равен нулю. [3]
Вход 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
Более быстрый способ предложен Продингером [4], где x — входные данные, np — строка положительных битов, а nm — строка отрицательных битов:
Вход x Выход np , нм xh = x >> 1; x3 = x + xh ; c = xh ^ x3 ; np = x3 & c ; нм = xh & c ;
который используется, например, в A184616.