Несмежная форма
| Часть серии о |
| Системы счисления |
|---|
| Список систем счисления |
( Несмежная форма NAF ) числа — это уникальное представление цифр со знаком , в котором ненулевые значения не могут быть соседними. Например:
- (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 это число снижается до одной трети всех цифр. Это приводит к эффективной реализации цепей сложения/вычитания (например, умножения на константу) в аппаратной цифровой обработке сигналов . [1]
Очевидно, что не более половины цифр отличны от нуля, поэтому это было введено Г.В. Рейтвейснером. [2] для ускорения ранних алгоритмов умножения, во многом похожих на кодирование Бута .
Поскольку каждая ненулевая цифра должна соседствовать с двумя нулями, представление NAF может быть реализовано так, что битами, требуется максимум m для значения, которое обычно представляется в двоичном виде с m + 1 бит .
Свойства NAF делают его полезным в различных алгоритмах, особенно в криптографии ; например, для уменьшения количества умножений, необходимых для возведения в степень . В алгоритме возведения в степень возведением в квадрат количество умножений зависит от количества ненулевых битов. Если показатель степени здесь указан в форме NAF, цифровое значение 1 подразумевает умножение по основанию, а цифровое значение -1 - на обратное.
Другие способы кодирования целых чисел, избегающие последовательных единиц, включают кодирование Бута и кодирование Фибоначчи .
Конвертация в НАФ
[ редактировать ]Существует несколько алгоритмов получения представления NAF значения, заданного в двоичном формате. Одним из таких является следующий метод с использованием многократного деления; он работает путем выбора ненулевых коэффициентов так, чтобы полученное частное делилось на 2 и, следовательно, следующий коэффициент был равен нулю. [3]
Input E = (em−1 em−2 ··· e1 e0)2
Output Z = (zm zm−1 ··· z1 z0)NAF
i ← 0
while E > 0 do
if E is odd then
zi ← 2 − (E mod 4)
E ← E − zi
else
zi ← 0
E ← E/2
i ← i + 1
return z
Более быстрый способ предлагает Prodinger. [4] где x — входные данные, np — строка положительных битов, а nm — строка отрицательных битов:
Input x Output np, nm xh = x >> 1; x3 = x + xh; c = xh ^ x3; np = x3 & c; nm = xh & c;
который используется, например, в A184616 .
Внешние ссылки
[ редактировать ]- Введение в каноническое представление знаковых цифр
- Коулман, Джо; Юрдакул А. (21–23 марта 2001 г.). Дроби в канонической знаково-цифровой системе счисления . Конференция по информационным наукам и системам. Университет Джонса Хопкинса. OCLC 48052559 .
Ссылки
[ редактировать ]- ^ Хьюлитт, РМ (2000). Каноническое представление цифр со знаком для цифровых фильтров FIR . Системы обработки сигналов, 2000. SiPS 2000. 2000 Семинар IEEE. стр. 416–426. дои : 10.1109/SIPS.2000.886740 . ISBN 978-0-7803-6488-2 . S2CID 122082511 .
- ^ Рейтвизнер, Джордж В. (1960). «Двоичная арифметика». Достижения в области компьютеров . 1 : 231–308. дои : 10.1016/S0065-2458(08)60610-5 . ISBN 9780120121014 .
- ^ Хэнкерсон, Д.; Менезес, А.; Ванстон, Ю.А. (2004). Руководство по криптографии на основе эллиптических кривых . Спрингер. п. 98. ИСБН 978-0-387-21846-5 .
- ^ Продингер, Хельмут. «О двоичных представлениях целых чисел с цифрами -1, 0, 1» (PDF) . Целые числа . Проверено 25 июня 2021 г.