Избыточное двоичное представление (RBR) является системой счисления , которая использует большее количество бит , чем требуется для представления одного двоичного разряда , так что большинство числа имеет несколько представлений. RBR отличается от обычных двоичных систем счисления , включая дополнение до двух , в которых для каждой цифры используется один бит. Многие свойства RBR отличаются от свойств обычных систем двоичного представления. Что наиболее важно, RBR позволяет добавлять без использования обычного переноса. [1] По сравнению с не избыточным представлением, RBR замедляет побитовые логические операции , но арифметические операции выполняются быстрее при использовании большей разрядности. [2]Обычно каждая цифра имеет свой знак, который не обязательно совпадает со знаком представленного числа. Когда цифры имеют знаки, этот RBR также является представлением цифры со знаком .
Конвертация из RBR
RBR - это система записи значений . В RBR цифры представляют собой пары битов, то есть для каждого места RBR использует пару битов. Значение, представленное избыточной цифрой, можно найти с помощью таблицы перевода. В этой таблице указаны математические значения каждой возможной пары битов.
Как и в обычном двоичном представлении, целочисленное значение данного представления представляет собой взвешенную сумму значений цифр. Вес начинается с 1 для крайней правой позиции и увеличивается в 2 раза для каждой следующей позиции. Обычно RBR допускает отрицательные значения. Нет единого знакового бита, который сообщает, является ли избыточно представленное число положительным или отрицательным. Большинство целых чисел имеют несколько возможных представлений в RBR.
Часто в качестве «канонической» формы выбирается одно из нескольких возможных представлений целого числа, поэтому каждое целое число имеет только одно возможное «каноническое» представление; несмежная форма и дополнение до двух - популярные варианты для этой канонической формы.
Целое значение может быть преобразован обратно из RBR с помощью следующей формулы, где п есть число цифр и й к является истолковано значение 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 ) времени.
Рекомендации
- ^ Phatak, Dhananjay S .; Корен, Израиль (август 1994 г.). «Гибридные системы счисления со знаком: унифицированная структура для представления избыточных чисел с ограниченными цепями распространения переноса» (PDF) . Транзакции IEEE на компьютерах . 43 (8): 880–891. CiteSeerX 10.1.1.352.6407 . DOI : 10.1109 / 12.295850 .
- ^ Лессард, Луи Филипп (2008). «Быстрая арифметика на ПЛИС с использованием избыточного двоичного аппарата» . Проверено 12 сентября 2015 .
- ^ Veeramachaneni, Sreehari; Кришна, М. Кирти; Авинаш, Лингамнени; Редди П., Срикант; Шринивас, МБ (май 2007 г.). Новый высокоскоростной избыточный двоичный преобразователь в двоичный с использованием префиксных сетей (PDF) . Международный симпозиум IEEE по схемам и системам (ISCAS 2007). Жители Нового Орлеана. DOI : 10.1109 / ISCAS.2007.378170 .
- ^ Лапойнт, Марсель; Huynh, Huu Tue; Фортье, Пол (апрель 1993 г.). «Систематический дизайн конвейерных рекурсивных фильтров». Транзакции IEEE на компьютерах . 42 (4): 413–426. DOI : 10.1109 / 12.214688 .
- ^ Ю-Тин Пай; Ю-Кумг Чен (январь 2004 г.). Самый быстрый сумматор упреждающего переноса (PDF) . Второй международный семинар IEEE по электронному проектированию, тестированию и применению (DELTA '04). Перт. DOI : 10,1109 / DELTA.2004.10071 .
- ^ Хосе, Биджой; Радхакришнан, Даму (декабрь 2006 г.). Оптимизированные по задержке избыточные двоичные сумматоры . 13-я Международная конференция IEEE по электронике, схемам и системам, 2006 г. (ICECS '06). Хороший. DOI : 10.1109 / ICECS.2006.379838 .