Nadmiarowa reprezentacja binarna - Redundant binary representation

Zbędne przedstawienie binarnego (RBR) jest systemie liczbowym zajmuje więcej bitów, niż to konieczne, aby reprezentować jeden binarny cyfrę tak, że większość numerów kilka wyjaśnień. RBR różni się od zwykłych binarnych systemów liczbowych , w tym uzupełnień do dwóch , które używają jednego bitu dla każdej cyfry. Wiele właściwości RBR różni się od właściwości zwykłych binarnych systemów reprezentacji. Co najważniejsze, RBR umożliwia dodanie bez użycia typowego przenoszenia. W porównaniu z reprezentacją nienadmiarową RBR powoduje, że operacje logiczne bitowe są wolniejsze, ale operacje arytmetyczne są szybsze, gdy używana jest większa szerokość bitowa. Zwykle każda cyfra ma swój własny znak, który niekoniecznie jest taki sam jak znak reprezentowanej liczby. Kiedy cyfry mają znaki, to RBR jest również reprezentacją cyfry ze znakiem .

Konwersja z RBR

RBR to system notacji wartości-miejsca . W RBR cyfry są parami bitów, to znaczy dla każdego miejsca RBR używa pary bitów. Wartość reprezentowaną przez nadmiarową cyfrę można znaleźć za pomocą tabeli tłumaczeń. Ta tabela wskazuje matematyczną wartość każdej możliwej pary bitów.

Podobnie jak w konwencjonalnej reprezentacji binarnej, wartość całkowita danej reprezentacji jest ważoną sumą wartości cyfr. Waga zaczyna się od 1 dla skrajnej prawej pozycji i wzrasta dwukrotnie dla każdej następnej pozycji. Zwykle RBR dopuszcza wartości ujemne. Nie ma bitu pojedynczego znaku, który mówi, czy nadmiarowo reprezentowana liczba jest dodatnia czy ujemna. Większość liczb całkowitych ma kilka możliwych reprezentacji w RBR.

Często jedna z kilku możliwych reprezentacji liczby całkowitej jest wybierana jako forma „kanoniczna”, więc każda liczba całkowita ma tylko jedną możliwą reprezentację „kanoniczną”; forma nieprzylegająca i dopełnienie do dwóch są popularnymi opcjami dla tej formy kanonicznej.

Całkowitą wartość może być przekształcany z powrotem z RBR za pomocą następującego wzoru, gdzie n oznacza liczbę cyfr oraz d _k jest interpretowane wartość k -tym cyfry, gdzie k zaczyna się na 0 w pozycji skrajnej prawej:

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

Konwersja z RBR do n- bitowego uzupełnienia do dwóch może być wykonana w czasie O (log ( n )) przy użyciu sumatora przedrostków .

Przykład redundantnej reprezentacji binarnej

Nie wszystkie nadmiarowe reprezentacje mają takie same właściwości. Na przykład, korzystając z tabeli tłumaczeń po prawej stronie, cyfrę 1 można przedstawić w tym RBR na wiele sposobów: „01 · 01 · 01 · 11" (0 + 0 + 0 + 1), "01 · 01 · 10 · 11 "(0 + 0 + 0 + 1)," 01 · 01 · 11 · 00 "(0 + 0 + 2−1) lub" 11 · 00 · 00 · 00 "(8−4−2−1) . Również dla tej tablicy translacji odwrócenie wszystkich bitów ( NIE bramka ) odpowiada znalezieniu odwrotności addytywnej ( mnożenie przez −1 ) reprezentowanej liczby całkowitej.

W tym przypadku: ${\ displaystyle d_ {k} \ in \ {- 1,0,1 \}}$

Działania arytmetyczne

Reprezentacje nadmiarowe są powszechnie używane w szybkich arytmetycznych jednostkach logicznych .

W szczególności sumator z zachowaniem przeniesienia używa redundantnej reprezentacji.

Dodanie

Schemat jednostki sumującej wykorzystującej pełny blok sumatora (z = x + y)

Operacja dodawania we wszystkich RBR jest bez przenoszenia, co oznacza, że ​​przenoszenie nie musi być propagowane przez całą szerokość jednostki dodającej. W efekcie dodatek we wszystkich RBR jest działaniem o stałym czasie. Dodawanie zawsze zajmie taką samą ilość czasu, niezależnie od szerokości bitowej operandów . Nie oznacza to, że dodawanie jest zawsze szybsze w RBR niż jego odpowiednik uzupełniający do dwóch , ale że dodawanie będzie ostatecznie szybsze w RBR ze zwiększającą się szerokością bitu, ponieważ opóźnienie jednostki dodawania uzupełnień do dwóch jest proporcjonalne do log ( n ) (gdzie n to szerokość bitowa). Dodawanie do RBR zajmuje stały czas, ponieważ każda cyfra wyniku może być obliczona niezależnie od siebie, co oznacza, że ​​każda cyfra wyniku może być obliczona równolegle.

Odejmowanie

Odejmowanie jest tym samym, co dodawanie, z tym wyjątkiem, że najpierw należy obliczyć addytywną odwrotność drugiego argumentu. W przypadku typowych reprezentacji można to zrobić na zasadzie cyfra po cyfrze.

Mnożenie

Wiele mnożników sprzętowych używa wewnętrznie kodowania Bootha , nadmiarowej reprezentacji binarnej.

Operacje logiczne

Bitowe operacje logiczne, takie jak AND , OR i XOR , nie są możliwe w redundantnych reprezentacjach. Chociaż możliwe jest wykonywanie operacji bitowych bezpośrednio na bazowych bitach wewnątrz RBR, nie jest jasne, czy jest to znacząca operacja; istnieje wiele sposobów przedstawiania wartości w RBR, a wartość wyniku zależy od zastosowanej reprezentacji.

Aby uzyskać oczekiwane wyniki, konieczne jest najpierw przekonwertowanie dwóch operandów na niepotrzebne reprezentacje. W konsekwencji operacje logiczne są wolniejsze w RBR. Dokładniej, zajmują one czas proporcjonalny do log ( n ) (gdzie n jest liczbą cyfr) w porównaniu do czasu stałego w uzupełnieniu do dwóch .

Możliwe jest jednak częściowe przekonwertowanie tylko najmniej znaczącej części nadmiarowo reprezentowanej liczby do postaci nienadmiarowej. Pozwala to na wykonywanie operacji, takich jak maskowanie niskich k bitów, w czasie log ( k ).

Bibliografia