Что такое формат канонической цифровой подписи?
Каноническая цифровая цифра (CSD) представляет собой тип представления числа.Важными характеристиками представления CSD являются:
- Представление номера CSD состоит из чисел 0, 1 и -1.[ 1 , 2 ].
- Представление номера CSD является уникальным [ 2 ].
- Номерненулевые цифры минимальны [ 2 ].
- Не может быть двух последовательных ненулевых цифр [ 2 ].
Как преобразовать число в его представление CSD?
Сначала найдите двоичное представление числа.
Пример 1 Давайте возьмем, например, число 287, которое является 1 0001 1111 в двоичном представлении.(256 + 16 + 8 + 4 + 2 + 1 = 287)
1 0001 1111
Начиная справа (LSB), если вы найдете больше, чем ненулевые элементы (1 или -1) в строке, возьми их все, плюс следующий ноль.(если слева от MSB нет нуля, создайте его там).Мы видим, что первая часть этого числа -
01 1111
Добавьте 1 к числу (т. Е. Измените 0 на 1 и все 1 на 0) и установите для крайней правой цифры значение -1.
01 1111 -> 10 000-1
Вы можете проверить, что число остается прежним: 16 + 8 + 4 + 2 + 1 = 31 = 32 + (-1).Теперь число выглядит следующим образом
1 0010 000-1
Поскольку последовательных ненулевых цифр больше нет, преобразование завершено.Таким образом, представление CSD для числа 287 составляет 1 0010 000-1, что составляет 256 + 31 - 1.
Пример 2
Как насчет немного более сложныхпример.Число 345. В двоичном виде это
1 0101 1001
Найти первое место (начиная справа), где в строке более одного ненулевого числа.Возьмите также следующий ноль.Добавьте к нему одну и сделайте так, чтобы крайняя правая цифра была равна -1.
1 0110 -1001
Теперь мы только что создали еще одну пару цифр, которую необходимо преобразовать.Возьмите 011 и добавьте к нему единицу (получите 100), и установите для последней цифры -1.(получите 10-1).Теперь число выглядит так:
1 10-10 -1001
Сделайте то же самое снова.На этот раз вам нужно будет представить ноль в левой части MSB.
10 -10-10 -1001
Вы можете убедиться, что это правильное представление CSD, наблюдая, что: 1) Нет последовательныхноль цифр.2) Сумма добавляется к 325 (512 - 128 - 32 - 8 + 1 = 345).
Более формальные определения этого алгоритма можно найти в [ 2 ].
Мотивация представления CSD
CSD может использоваться и в некоторых других приложениях, но это перспектива цифровой микроэлектроники.Это часто используется в цифровом умножении.[ 1 , 2 ].Цифровое умножение состоит из двух этапов: вычисление частичных произведений и суммирование частичных произведений.Рассмотрим умножение 1010 и 1011:
1010
x 1011
1010
1010
0000
+ 1010
= 1101110
Как видим, число ненулевых частичных произведений (1091 * s), которые должны быть суммированы, зависит от количества ненулевых цифр в множителе.Таким образом, время вычисления суммы частичных произведений зависит от количества ненулевых цифр в умножителе.Поэтому цифровое умножение с использованием преобразованных чисел CSD происходит быстрее, чем с использованием обычных цифровых чисел.Форма CSD содержит на 33% меньше ненулевых цифр, чем двоичное представление (в среднем).Например, обычное умножение с плавающей запятой двойной точности может занять 100,2 нс, но только 93,2 нс, при использовании представления CSD.[ 1 ]
А как насчет отрицательных?Есть ли на самом деле три состояния (уровни напряжения) в микросхеме?Нет, частичные произведения, рассчитанные с отрицательным знаком, не суммируются сразу.Вместо этого вы добавляете 2 дополнения (т.е. отрицательное представление) этих чисел к окончательной сумме.
Источники:
[ 1 ] Д. Харини Шарма, Адданки Пурна Рамеш: Множитель с плавающей запятой с использованием канонической цифры со знаком
[ 2 ] ГуставоА. Руис, Mercedes Grand: Эффективное каноническое цифровое перекодирование со знаком