Dodatek do przenoszenia

Sumator typu carry-save to rodzaj sumatora cyfrowego , który służy do wydajnego obliczania sumy trzech lub więcej liczb binarnych . Różni się od innych sumatorów cyfrowych tym, że wyprowadza dwie (lub więcej) liczby, a odpowiedź pierwotnego sumowania można uzyskać, dodając te wyjścia do siebie. Sumator z zapisem przenoszenia jest zwykle używany w mnożniku binarnym, ponieważ mnożnik binarny wymaga dodania więcej niż dwóch liczb binarnych po pomnożeniu. Duży sumator zaimplementowany przy użyciu tej techniki będzie zwykle znacznie szybszy niż konwencjonalne dodawanie tych liczb.

Motywacja

Rozważ sumę:

12345678 + 87654322 = 100000000

Korzystając z podstawowej arytmetyki, obliczamy od prawej do lewej, „8 + 2 = 0, przenieś 1”, „7 + 2 + 1 = 0, przenieś 1”, „6 + 3 + 1 = 0, przenieś 1” i tak dalej do końca sumy. Chociaż znamy ostatnią cyfrę wyniku od razu, nie możemy znać pierwszej cyfry, dopóki nie przejdziemy przez wszystkie cyfry w obliczeniach, przekazując przeniesienie z każdej cyfry do tej po jej lewej stronie. Zatem dodanie dwóch n -cyfrowych liczb musi zająć czas proporcjonalny do n , nawet jeśli maszyna, której używamy, byłaby w stanie wykonać wiele obliczeń jednocześnie.

W ujęciu elektronicznym przy użyciu bitów (cyfr binarnych) oznacza to, że nawet jeśli mamy do dyspozycji n jednobitowych sumatorów, to i tak musimy zapewnić czas proporcjonalny do n , aby możliwe przeniesienie przeniosło się z jednego końca liczby do drugiego. Dopóki tego nie zrobimy,

1. Nie znamy wyniku dodawania.
2. Nie wiemy, czy wynik dodawania jest większy, czy mniejszy od podanej liczby (np. nie wiemy, czy jest dodatni, czy ujemny).

carry look-ahead może zmniejszyć opóźnienie. Zasadniczo opóźnienie można zmniejszyć tak, aby było proporcjonalne do log n , ale w przypadku dużych liczb już tak nie jest, ponieważ nawet po zaimplementowaniu przeniesienia z wyprzedzeniem odległości, które sygnały muszą pokonać na chipie, zwiększają się proporcjonalnie do n , a opóźnienia propagacji rosną w tym samym tempie. Gdy dojdziemy do rozmiarów liczb od 512 do 2048 bitów, które są wymagane w kryptografii z kluczem publicznym , przewidywanie przeniesienia nie jest zbyt pomocne.

Podstawowa koncepcja

Pomysł odkładania rozwiązania przenoszenia do końca lub oszczędzania przenoszenia pochodzi od Johna von Neumanna .

Suma dwóch cyfr nigdy nie może zawierać więcej niż 1, a suma dwóch cyfr plus 1 również nigdy nie może zawierać więcej niż 1. Na przykład w systemie dziesiętnym ${\ Displaystyle 9 + 9 = 18$ } który niesie 1; ${\ Displaystyle 9 + 9 + 1 = 19}$ , który również przenosi 1. Dodając trzy cyfry, możemy dodać dwie pierwsze i utworzyć sumę oraz cyfry przenoszenia; następnie dodaj sumę i cyfry przenoszenia do trzeciej cyfry i utwórz sumę i cyfry przenoszenia. W systemie binarnym jedynymi cyframi są zero i jedynka, więc , $\ Displaystyle 0$$+ 1 = 1}$ i $Displaystyle 1 + 1 = 0}$$jest$ przeniesioną 1. Dodanie przeniesionego bitu może dać co najwyżej , więc możliwe Z tego powodu możliwe jest również dodanie pierwszych trzech cyfr i wyliczenie sumy i przeniesienia; dla kolejnych cyfr suma i przeniesienie to dwa wyrazy, do których dodaje się następną pojedynczą cyfrę.

Oto przykład sumy binarnej 3 długich liczb binarnych:

10111010101011011111000000001101 a) + 11011110101011011011111011101111 b) + 00010010101101110101001101010010 c)

Konwencjonalnym sposobem na to byłoby najpierw obliczenie (a+b), a następnie obliczenie ((a+b)+c). Arytmetyka z zapisywaniem przenoszenia działa poprzez rezygnację z wszelkiego rodzaju propagacji przenoszenia. Oblicza sumę cyfra po cyfrze, jako:

10111010101011011111000000001101 + 11011110101011011011111011101111 + 000100101011011110101001101010010 = 2113213030312313222 3112112112222

Notacja jest niekonwencjonalna, ale wynik jest nadal jednoznaczny. Jeśli założymy, że te trzy liczby to a, b i c. Tutaj wynik będzie opisany jako suma 2 liczb binarnych, gdzie pierwsza liczba, S, jest po prostu sumą otrzymaną przez dodanie cyfr (bez żadnej propagacji przeniesienia), tj. S i = a _i ⊕ _b i _⊕ c _i oraz druga liczba, C, składa się z przeniesień z poprzednich sum indywidualnych, czyli C _i+1 = (a _i b _i ) + (b _i c _i ) + (c _i a _i ) :

01110110101101110001110110110000 i 1001101010101101111110010010011110

Teraz te 2 liczby można wysłać do sumatora propagującego przenoszenie, który wyświetli wynik.

Było to bardzo korzystne z punktu widzenia opóźnienia (czasu obliczeń). Gdyby dodać te 3 liczby przy użyciu konwencjonalnych metod, dotarcie do odpowiedzi zajęłoby 2 opóźnienia sumatora propagacji przeniesienia. Jeśli używasz techniki carry-save, potrzebujesz tylko 1 opóźnienia sumatora propagacji przenoszenia i jednego opóźnienia pełnego sumatora (co jest znacznie mniejsze niż opóźnienie propagacji przenoszenia). Zatem sumatory CSA są zazwyczaj bardzo szybkie.

Akumulatory typu „carry-save”.

Zakładając, że mamy dwa bity pamięci na cyfrę, możemy użyć redundantnej reprezentacji binarnej , przechowując wartości 0, 1, 2 lub 3 na każdej pozycji cyfry. Jest zatem oczywiste, że do naszego wyniku przeniesienia można dodać jeszcze jedną liczbę binarną bez przepełnienia naszej pojemności pamięci: ale co wtedy?

Kluczem do sukcesu jest to, że w momencie każdego dodania cząstkowego dodajemy trzy bity:

• 0 lub 1, od liczby, którą dodajemy.
• 0, jeśli cyfra w naszym sklepie to 0 lub 2, lub 1, jeśli jest to 1 lub 3.
• 0, jeśli cyfra po prawej stronie to 0 lub 1, lub 1, jeśli jest to 2 lub 3.

Innymi słowy, bierzemy cyfrę przenoszenia z pozycji po naszej prawej stronie i przekazujemy cyfrę przenoszenia w lewo, tak jak w konwencjonalnym dodawaniu; ale cyfra przenoszenia, którą przekazujemy po lewej stronie, jest wynikiem poprzedniego obliczenia, a nie bieżącego. W każdym cyklu zegara nośniki muszą przesunąć się tylko o jeden krok, a nie o n kroków, jak w konwencjonalnym dodawaniu.

Ponieważ sygnały nie muszą przemieszczać się tak daleko, zegar może tykać znacznie szybciej. ..

Nadal istnieje potrzeba przekonwertowania wyniku na binarny na końcu obliczeń, co w rzeczywistości oznacza po prostu pozwolenie przeniesieniom na przejście przez całą liczbę, tak jak w konwencjonalnym sumatorze. Ale jeśli wykonaliśmy 512 dodań w trakcie wykonywania 512-bitowego mnożenia, koszt tej ostatecznej konwersji jest efektywnie podzielony na te 512 dodań, więc każde dodawanie ponosi 1/512 kosztu tego końcowego „konwencjonalnego” dodania.

Wady

Na każdym etapie dodania opcji carry-save,

1. Wynik dodawania znamy od razu.
2. Nadal nie wiemy, czy wynik dodawania jest większy, czy mniejszy od podanej liczby (np. nie wiemy, czy jest dodatni, czy ujemny).

Ten ostatni punkt jest wadą w przypadku używania sumatorów typu carry-save do implementacji mnożenia modułowego (mnożenie, po którym następuje dzielenie, zachowując tylko resztę). Jeśli nie możemy wiedzieć, czy wynik pośredni jest większy, czy mniejszy niż moduł, skąd możemy wiedzieć, czy odjąć moduł?

Mnożenie Montgomery'ego , które zależy od skrajnej prawej cyfry wyniku, jest jednym rozwiązaniem; chociaż raczej podobnie jak samo dodawanie z oszczędnością przenoszenia, niesie ze sobą stały narzut, tak że sekwencja mnożeń Montgomery'ego oszczędza czas, ale jedno nie. Na szczęście potęgowanie, które w rzeczywistości jest sekwencją mnożenia, jest najczęstszą operacją w kryptografii klucza publicznego.

Dokładna analiza błędów pozwala na dokonanie wyboru dotyczącego odejmowania modułu, nawet jeśli nie wiemy na pewno, czy wynik dodawania jest wystarczająco duży, aby uzasadnić odejmowanie. Aby to zadziałało, konieczne jest, aby projekt obwodu mógł dodać −2, −1, 0, +1 lub +2 razy moduł. Przewaga nad mnożeniem Montgomery'ego polega na tym, że nie ma stałego narzutu związanego z każdą sekwencją mnożenia.

Szczegóły techniczne

Jednostka typu carry-save składa się z n pełnych sumatorów , z których każdy oblicza pojedynczą sumę i bit przenoszenia wyłącznie na podstawie odpowiednich bitów trzech liczb wejściowych. Biorąc pod uwagę trzy n -bitowe liczby a , b i c , daje to sumę częściową ps i przeniesienie przesunięcia sc :

${\ Displaystyle ps_ {i} = a_ {i} \ oplus b_ {i} \ oplus c_ {i}}$

${\ Displaystyle sc_ {i} = (a_ {i} \ klin b_ {i}) \ vee (a_ {i} \ klin c_ {i}) \ vee (b_ {i} \ klin c_ {i}).}$

Całą sumę można następnie obliczyć za pomocą:

1. Przesunięcie sekwencji przenoszenia sc w lewo o jedno miejsce.
2. Dodanie 0 na początku ( najbardziej znaczący bit ) sekwencji sumy częściowej ps .
3. Używając sumatora przeniesienia tętnienia , aby dodać te dwa elementy i uzyskać wynikową wartość ( n + 1)-bitową.

Zobacz też

• Drzewo Wallace'a

Dalsza lektura

• Savard, John JG (2018) [2006]. „Zaawansowane techniki arytmetyczne” . czworokąt . Zarchiwizowane od oryginału w dniu 2018-07-03 . Źródło 2018-07-16 .