이중 이항 표현

중복이진표현(RBR)은 대부분의 숫자가 여러 개의 표현을 갖도록 하나의 이진수를 나타내기 위해 필요 이상으로 많은 비트를 사용하는 숫자 시스템이다.RBR은 각 자릿수에 대해 하나의 비트를 사용하는 두 개의 보완을 포함한 일반적인 2진수 시스템과 다르다.RBR의 많은 특성은 일반 이항 표현 시스템의 특성과는 다르다.가장 중요한 것은 RBR이 일반적인 캐리어를 사용하지 않고도 추가할 수 있다는 것이다.^[1]비중복 표현과 비교할 때, RBR은 비트 논리 연산을 더 느리게 하지만, 더 큰 비트 폭을 사용할 때 산술 연산이 더 빠르다.^[2]일반적으로 각 자리에는 반드시 나타내는 숫자의 부호와 같지 않은 고유한 부호가 있다.숫자에 기호가 있을 때, RBR은 또한 서명된 숫자 표현이다.

RBR로부터의 변환

RBR은 장소-값 표기법이다.RBR에서 자릿수는 비트 쌍이며, 즉 모든 위치에 대해 RBR은 비트 쌍을 사용한다.중복 숫자로 대표되는 값은 번역표를 사용하여 찾을 수 있다.이 표는 가능한 각 비트 쌍의 수학적 값을 나타낸다.

기존의 이항 표현에서와 같이, 주어진 표현에 대한 정수 값은 자릿수 값의 가중치 합이다.무게는 가장 오른쪽 위치의 경우 1에서 시작하여 다음 위치의 경우 2배씩 올라간다.보통 RBR은 음의 값을 허용한다.중복으로 표시된 숫자가 양수인지 음수인지를 알려주는 단일 기호 비트는 없다.대부분의 정수는 RBR에서 몇 가지 가능한 표현을 가지고 있다.

종종 정수의 가능한 표현들 중 하나는 "캐논어" 형태로 선택되기 때문에, 각각의 정수는 오직 하나의 가능한 "캐논어적" 표현만을 가지고 있다; 비인접적 형태와 두 개의 보완물은 그 표준형식에 인기 있는 선택이다.

정수 값은 다음 공식을 사용하여 RBR에서 다시 변환할 수 있으며, 여기서 n은 자릿수, d는_k k번째 자릿수의 해석 값이며, 여기서 k는 가장 오른쪽 위치에서 0에서 시작한다.

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

RBR에서 n-bit 2의 보어로의 변환은 접두사 애더기를 사용하여 O(log(n) 시간에 수행될 수 있다.^[3]

이중화된 이진 표현 예제

숫자에 대한 변환 테이블 예제

숫자	해석값
00	−1
01	0
10	0
11	1

모든 중복 표현들이 동일한 속성을 갖는 것은 아니다.For example, using the translation table on the right, the number 1 can be represented in this RBR in many ways: "01·01·01·11" (0+0+0+1), "01·01·10·11" (0+0+0+1), "01·01·11·00" (0+0+2−1), or "11·00·00·00" (8−4−2−1).또한 이 번역표의 경우, 모든 비트(NOT 게이트)를 뒤집는 것은 표시된 정수의 가법역(-1)을 찾는 것과 일치한다.^[4]

이 경우: $d{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}${${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle d_{k}\in \{-1,1\}}$

산술 연산

중복 표현은 일반적으로 고속 산술 논리 단위 안에서 사용된다.

특히 휴대품 저장 애더는 중복 표현을 사용한다.^{[citation needed]}

덧셈

모든 RBR에서 추가 작업은 무반입으로 수행되며, 이는 추가 장치의 전체 폭을 통해 캐리어가 전파될 필요가 없다는 것을 의미한다.사실상 모든 RBR에 추가되는 것은 일정한 시간 운용이다.추가는 항상 피연산자의 비트 폭과 독립적으로 동일한 시간이 소요된다.이는 추가가 항상 RBR에서 두 보완적 등가물보다 빠르다는 것을 의미하는 것이 아니라, 두 보완적 추가 장치의 지연이 로그(n)에 비례하기 때문에(여기서 n은 비트 폭)가 증가하는 RBR에서 추가가 더 빠를 것이라는 것을 의미한다.^[5]결과의 각 자릿수는 서로 독립적으로 계산될 수 있기 때문에 RBR을 추가하면 결과의 각 자릿수를 병렬로 계산할 수 있다는 것을 의미하기 때문에 일정한 시간이 걸린다.^[6]

뺄셈

뺄셈은 두 번째 피연산자의 가법역비를 먼저 계산해야 한다는 점을 제외하면 덧셈과 같다.일반적인 표현에 대해, 이것은 자릿수 단위로 이루어질 수 있다.

곱하기

많은 하드웨어 승수들이 내부적으로 중복 바이너리 표현인 Booth 인코딩을 사용한다.

논리 연산

AND, OR, XOR와 같은 비트 논리 연산은 중복 표현에서 가능하지 않다.RBR 내부의 기본 비트에서 직접 비트 연산을 할 수 있지만, 이것이 의미 있는 연산인지는 확실하지 않다. RBR에서 값을 나타내는 여러 가지 방법이 있으며, 결과의 값은 사용된 표현에 따라 달라질 것이다.

예상되는 결과를 얻기 위해서는 우선 두 피연산자를 비중복 표현으로 전환해야 한다.따라서 논리 연산은 RBR에서 더 느리다.더 정확히 말하면, 그들은 두 개의 보어에서의 일정한 시간에 비해 로그(n)에 비례하는 시간이 걸린다.

그러나 중복으로 표시된 숫자의 중요도가 가장 낮은 부분만 비중복 형태로 부분적으로 변환하는 것은 가능하다.이를 통해 로우 k 비트를 마스킹하는 등의 작업을 로그(k) 시간에 수행할 수 있다.

참조