Избыточное двоичное представление - Redundant binary representation

А избыточное двоичное представление (RBR) это система счисления который использует больше бит, чем необходимо для представления одного двоичного файла цифра так что большинство чисел имеет несколько представлений. RBR не похож на обычный двоичная система счисления, включая два дополнения, которые используют один бит для каждой цифры. Многие свойства RBR отличаются от свойств обычных систем двоичного представления. Что наиболее важно, RBR позволяет добавлять без использования обычного переноса.^[1] По сравнению с не избыточным представлением, RBR делает побитовая логическая операция медленнее, но арифметические операции работают быстрее, когда используется большая разрядность.^[2] Обычно каждая цифра имеет свой знак, который не обязательно совпадает со знаком представленного числа. Когда у цифр есть знаки, RBR также является представление цифр со знаком.

Конвертация из RBR

RBR - это система обозначений мест. В RBR цифры находятся пары бит, то есть для каждого места RBR использует пару битов. Значение, представленное избыточной цифрой, можно найти с помощью таблицы перевода. В этой таблице указаны математические значения каждой возможной пары битов.

Как и в обычном двоичном представлении, целое число значение данного представления - это взвешенная сумма значений цифр. Вес начинается с 1 для крайней правой позиции и увеличивается в 2 раза для каждой следующей позиции. Обычно RBR допускает отрицательные значения. Нет единого знакового бита, который указывает, является ли избыточно представленное число положительным или отрицательным. Большинство целых чисел имеют несколько возможных представлений в RBR.

Часто в качестве «канонической» формы выбирается одно из нескольких возможных представлений целого числа, поэтому каждое целое число имеет только одно возможное «каноническое» представление; несмежная форма и дополнение до двух - популярные варианты этой канонической формы.

An целое число значение можно преобразовать обратно из RBR с помощью следующей формулы, где п это количество цифр и d_k интерпретируемое значение k-я цифра, где k начинается с 0 в крайнем правом положении:

{displaystyle sum _ {k = 0} ^ {n-1} d_ {k} 2 ^ {k}}

Преобразование из RBR в п-битовое дополнение до двух может быть выполнено за O (log (п)) время с помощью префиксный сумматор.^[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]

В этом случае: ${displaystyle d_ {k} in {-1,0,1}}$

Арифметические операции

Избыточные представления обычно используются внутри высокоскоростных арифметико-логические устройства.

В частности, переносной сумматор использует избыточное представление.^{[нужна цитата ]}

Добавление

Схема сумматора с использованием полный сумматор блок (z = x + y)

Операция добавления во всех RBR не требует переноса, что означает, что перенос не должен распространяться по всей ширине блока добавления. Фактически, добавление во все RBR - это операция с постоянным временем. Добавление всегда будет занимать одинаковое количество времени независимо от разрядности операнды. Это не означает, что добавление всегда выполняется быстрее в RBR, чем его два дополнения эквивалентно, но что в конечном итоге сложение будет быстрее в RBR с увеличивающейся разрядностью, потому что задержка двух дополнительных модулей сложения пропорциональна log (п) (куда п это разрядность).^[5] Добавление в RBR занимает постоянное время, поскольку каждая цифра результата может быть вычислена независимо друг от друга, что означает, что каждая цифра результата может быть вычислена параллельно.^[6]

Вычитание

Вычитание такое же, как и сложение, за исключением того, что сначала необходимо вычислить аддитивное значение, обратное второму операнду. Для обычных представлений это может быть сделано по цифре.

Умножение

Много аппаратные умножители внутреннее использование Кодирование будки, избыточное двоичное представление.

Логические операции

Побитовые логические операции, такие как И, ИЛИ ЖЕ и XOR, невозможны в избыточных представлениях. Пока можно делать побитовые операции непосредственно на нижележащих битах внутри RBR, неясно, является ли это значимой операцией; есть много способов представить значение в RBR, и значение результата будет зависеть от используемого представления.

Чтобы получить ожидаемые результаты, необходимо сначала преобразовать два операнда в неизбыточные представления. Следовательно, логические операции в RBR выполняются медленнее. Точнее, они занимают время, пропорциональное log (п) (куда п это количество цифр) по сравнению с постоянным временем в два дополнения.

Однако возможно частично преобразовать только наименее значимую часть избыточно представленного числа в неизбыточную форму. Это позволяет выполнять такие операции, как маскирование низких k бит можно сделать в журнале (k) время.

Рекомендации

^ Phatak, Dhananjay S .; Корен, Израиль (август 1994 г.). «Гибридные системы чисел со знаком: унифицированная структура для представления избыточных чисел с ограниченными цепями распространения переноса» (PDF). Транзакции IEEE на компьютерах. 43 (8): 880–891. CiteSeerX 10.1.1.352.6407. Дои:10.1109/12.295850.
^ Лессард, Луи Филипп (2008). «Быстрая арифметика на ПЛИС с использованием избыточного двоичного аппарата». Получено 2015-09-12.
^ Veeramachaneni, Sreehari; Кришна, М. Кирти; Авинаш, Лингамнени; Редди П., Срикант; Шринивас, М. (Май 2007 г.). Новый высокоскоростной двоичный преобразователь в двоичный с резервированием с использованием префиксных сетей (PDF). Международный симпозиум IEEE по схемам и системам (ISCAS 2007). Жители Нового Орлеана. Дои:10.1109 / ISCAS.2007.378170.
^ Лапойнт, Марсель; Huynh, Huu Tue; Фортье, Пол (апрель 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.

[1] Phatak, Dhananjay S .; Корен, Израиль (август 1994 г.). «Гибридные системы чисел со знаком: унифицированная структура для представления избыточных чисел с ограниченными цепями распространения переноса» (PDF). Транзакции IEEE на компьютерах. 43 (8): 880–891. CiteSeerX 10.1.1.352.6407. Дои:10.1109/12.295850.

[2] Лессард, Луи Филипп (2008). «Быстрая арифметика на ПЛИС с использованием избыточного двоичного аппарата». Получено 2015-09-12.

[3] Veeramachaneni, Sreehari; Кришна, М. Кирти; Авинаш, Лингамнени; Редди П., Срикант; Шринивас, М. (Май 2007 г.). Новый высокоскоростной двоичный преобразователь в двоичный с резервированием с использованием префиксных сетей (PDF). Международный симпозиум IEEE по схемам и системам (ISCAS 2007). Жители Нового Орлеана. Дои:10.1109 / ISCAS.2007.378170.

[4] Лапойнт, Марсель; Huynh, Huu Tue; Фортье, Пол (апрель 1993 г.). «Систематический дизайн конвейерных рекурсивных фильтров». Транзакции IEEE на компьютерах. 42 (4): 413–426. Дои:10.1109/12.214688.

[5] Ю-Тин Пай; Ю-Кумг Чен (январь 2004 г.). Самый быстрый сумматор с упреждением (PDF). Второй международный семинар IEEE по электронному проектированию, тестированию и применению (DELTA '04). Перт. Дои:10.1109 / DELTA.2004.10071.

[6] Хосе, Биджой; Радхакришнан, Даму (декабрь 2006 г.). Оптимизированные по задержке избыточные двоичные сумматоры. 13-я Международная конференция IEEE по электронике, схемам и системам, 2006 г. (ICECS '06). Отлично. Дои:10.1109 / ICECS.2006.379838.

[1]

[2]

[3]

[4]

[5]

[6]