Избыточное двоичное представление
Избыточное двоичное представление (RBR) — это система счисления , в которой для представления одной двоичной цифры используется больше битов, чем необходимо , поэтому большинство чисел имеют несколько представлений. RBR отличается от обычных двоичных систем счисления , включая дополнение до двух , в которых для каждой цифры используется один бит. Многие свойства RBR отличаются от свойств обычных двоичных систем представления. Самое главное, что RBR позволяет складывать без использования обычного переноса. [1] По сравнению с неизбыточным представлением, RBR замедляет побитовые логические операции , но арифметические операции выполняются быстрее, когда используется большая разрядность. [2] Обычно каждая цифра имеет свой знак, который не обязательно совпадает со знаком изображаемого числа. Если у цифр есть знаки, RBR также является представлением знаковых цифр .
Конвертация из RBR
[ редактировать ]RBR — это система обозначений разрядных значений . В RBR цифры представляют собой пары битов, то есть для каждого места RBR использует пару битов. Значение, представленное избыточной цифрой, можно найти с помощью таблицы перевода. В этой таблице указано математическое значение каждой возможной пары битов.
Как и в обычном двоичном представлении, целочисленное значение данного представления представляет собой взвешенную сумму значений цифр. Вес начинается с 1 для самой правой позиции и увеличивается в 2 раза для каждой следующей позиции. Обычно RBR допускает отрицательные значения. Не существует единого знакового бита, который бы определял, является ли избыточно представленное число положительным или отрицательным. Большинство целых чисел имеют несколько возможных представлений в RBR.
Часто одно из нескольких возможных представлений целого числа выбирается в качестве «канонической» формы, поэтому каждое целое число имеет только одно возможное «каноническое» представление; несмежная форма и дополнение до двух являются популярным выбором для этой канонической формы.
Целочисленное n значение можно преобразовать обратно из RBR, используя следующую формулу, где — количество цифр, а d k — интерпретированное значение k -й цифры, где k начинается с 0 в крайнем правом положении:
Преобразование из RBR в n -битное дополнение до двух может быть выполнено за время O(log( n )) с использованием префиксного сумматора . [3]
Пример избыточного двоичного представления
[ редактировать ]| цифра | Интерпретированное значение |
|---|---|
| 00 | −1 |
| 01 | 0 |
| 10 | 0 |
| 11 | 1 |
Не все избыточные представления имеют одинаковые свойства. Например, используя таблицу перевода справа, число 1 можно представить в этом RBR разными способами: «01·01·01·11» (0+0+0+1), «01·01·10· 11 дюймов (0+0+0+1), «01·01·11·00» (0+0+2-1) или «11·00·00·00» (8-4-2-1) . Кроме того, для этой таблицы перевода переворот всех битов ( НЕ-вентиль ) соответствует нахождению аддитивного обратного значения ( умножение на -1 ) представленного целого числа. [4]
В этом случае:
Арифметические операции
[ редактировать ]Избыточные представления обычно используются внутри быстродействующих арифметико-логических устройств .
В частности, сумматор с сохранением переноса использует избыточное представление. [ нужна ссылка ]
Добавление
[ редактировать ]
Операция сложения во всех RBR не содержит переноса, что означает, что переносу не обязательно распространяться по всей ширине единицы сложения. По сути, сложение во всех RBR является операцией постоянного времени. Сложение всегда будет занимать одинаковое количество времени, независимо от разрядности операндов . Это не означает, что сложение в RBR всегда происходит быстрее, чем его эквивалент с дополнением до двух , но что сложение в конечном итоге будет быстрее в RBR с увеличением разрядности, поскольку задержка единицы сложения дополнения до двух пропорциональна log( n ) (где n — разрядность). [5] Сложение в RBR занимает постоянное время, поскольку каждая цифра результата может быть вычислена независимо друг от друга, а это означает, что каждая цифра результата может рассчитываться параллельно. [6]
Вычитание
[ редактировать ]Вычитание аналогично сложению, за исключением того, что сначала необходимо вычислить аддитивную величину, обратную второму операнду. Для обычных представлений это можно сделать по цифрам.
Умножение
[ редактировать ]Многие аппаратные умножители внутренне используют кодировку Бута , избыточное двоичное представление.
Логические операции
[ редактировать ]Побитовые логические операции, такие как AND , OR и XOR , невозможны в избыточных представлениях. Хотя можно выполнять побитовые операции непосредственно над базовыми битами внутри RBR, неясно, является ли это значимой операцией; существует множество способов представления значения в RBR, и значение результата будет зависеть от используемого представления.
Чтобы получить ожидаемые результаты, необходимо сначала преобразовать два операнда в неизбыточные представления. Следовательно, логические операции в RBR выполняются медленнее. Точнее, они занимают время, пропорциональное log( n ) (где n — количество цифр) по сравнению с постоянным временем в дополнении до двух .
Однако возможно частично преобразовать только наименее значимую часть избыточно представленного числа в неизбыточную форму. такие операции, как маскирование младших k Это позволяет выполнять битов, за время log( k ).
Ссылки
[ редактировать ]- ^ Фатак, Дхананджай С.; Корен, Израиль (август 1994 г.). «Гибридные системы счисления со знаковыми цифрами: унифицированная структура для представлений избыточных чисел с ограниченными цепочками распространения переноса» (PDF) . Транзакции IEEE на компьютерах . 43 (8): 880–891. CiteSeerX 10.1.1.352.6407 . дои : 10.1109/12.295850 .
- ^ Лессард, Луи-Филипп (2008). «Быстрая арифметика на FPGA с использованием избыточного двоичного устройства» . Проверено 12 сентября 2015 г.
- ^ Вирамачанени, Шрихари; Кришна, М. Кирти; Авинаш, Лингамнени; Редди П., Срикант; Шринивас, МБ (май 2007 г.). Новый высокоскоростной резервированный преобразователь двоичных сигналов в двоичные файлы с использованием префиксных сетей (PDF) . Международный симпозиум IEEE по схемам и системам (ISCAS 2007). Новый Орлеан. дои : 10.1109/ISCAS.2007.378170 .
- ^ Лапуант, Марсель; Хюинь, Хуу Туэ; Фортье, Пол (апрель 1993 г.). «Систематическое проектирование конвейерных рекурсивных фильтров». Транзакции IEEE на компьютерах . 42 (4): 413–426. дои : 10.1109/12.214688 .
- ^ Ю-Тин Пай; Ю-Кумг Чен (январь 2004 г.). Самый быстрый сумматор с упреждающим переносом (PDF) . Второй международный семинар IEEE по проектированию, тестированию и применению электроники (DELTA '04). Перт. дои : 10.1109/DELTA.2004.10071 .
- ^ Хосе, Биджой; Радхакришнан, Даму (декабрь 2006 г.). Двоичные сумматоры с оптимизированной задержкой . 13-я Международная конференция IEEE по электронике, схемам и системам, 2006 г. (ICECS '06). Хороший. дои : 10.1109/ICECS.2006.379838 .