Zaloguj się
Wszystkie
13 sierpnia 2024
109
Najwygodniejszym sposobem na przekonwertowanie liczby zapisanej binarnie na format dziesiętny jest użycie kodu BCD (binary coded decimal). Każdą cyfrę dziesiętną zapisujemy jako 4-bitową liczbę binarną. Cztery bity dają możliwość utworzenia 16 kombinacji, ale w kodzie BCD stosujemy tylko kombinacje od 0 do 9, a pozostałe są nieużywane.
Przykładowo: liczba dziesiętna 1234 zapisana w kodzie BCD będzie mieć 16-bitów i przyjmie postać 0001_0010_0011_0100. W kodzie binarnym byłoby to 100_1101_0010, czyli 11 bitów. Widzimy więc, że kod BCD nie jest optymalny, jeśli chodzi o zużycie zasobów, jednak pozwala w dość łatwy sposób operować na liczbach dziesiętnych.
Jak działa algorytm Double Dabble?
Najprościej będzie to wytłumaczyć na przykładzie. Chcemy przekształcić 8-bitową liczbę 113 na kod BCD. Jej binarna reprezentacja to 0b01110001. Umieszczamy ją w tabeli w kolumnie „Binarnie” i jest to stan początkowy algorytmu. Liczba ta jest 3-cyfrowa, zatem musimy przygotować trzy kolumny w tabeli – dla cyfr setek, dziesiątek i jedności – a każda z nich będzie miała 4 bity. Z tych kolumn odczytamy wynik w kodzie BCD.
W celu zwiększenia czytelności, w tabeli pominąłem wszystkie bity, które są nieistotne. We wszystkich pustych komórkach należy wpisać zero.
Algorytm Double Dabble polega na wykonywaniu w pętli dwóch operacji. Pierwszą z nich jest przesunięcie wszystkich rejestrów o jeden bit w lewo. Takie przesuwanie liczb binarnych jest równoznaczne z pomnożeniem przez 2 – stąd angielska nazwa double. Następnie, sprawdzamy każdą z cyfr. Jeżeli jest większa lub równa 5, wtedy dodajemy do niej 3 – jest to faza dabble. Przesunięć musi być tyle, ile bitów ma liczba na wejściu.
Zobaczmy, jak to działa:
- W kroku 1 przesuwamy w lewo liczbę, którą mieliśmy na wejściu. Cyfry setek, dziesiątek i jedności wciąż są zerami.
- Przechodzimy do kroku 2. Ponownie przesuwamy wszystkie rejestry. Cyfra jedności stała się jedynką. Jest to mniej niż 5, więc idziemy dalej.
- Następnie, w kroku 3, po raz kolejny przesuwamy wszystko w lewo. Cyfra jedności to 0b0011, czyli dziesiętnie 3, a więc wciąż mniej niż 5.
- W kroku 4A ponownie przesuwamy rejestry. Okazuje się, że po przesunięciu, cyfra jedności jest równa 0b0111 (zaznaczone na czerwono), czyli dziesiętnie 7. Zatem w kroku 4B musimy dodać do niej 3, co w rezultacie daje 10, czyli binarnie 0b1010.
- W kroku 5 ponownie przesuwamy. Wszystkie cyfry są mniejsze od 5.
- Podczas kroku 6A przesuwamy i sprawdzamy. Okazuje się, że cyfra jedności to 0b1000, czyli dziesiętnie 8. Zatem w kroku 6B dodajemy 3 i dostajemy 11, czyli binarnie 0b1011.
- Następnie znów przesuwamy wszystkie rejestry w kroku 7A. Sprawdzamy wszystkie cyfry. Okazuje się, że jednocześnie cyfra dziesiątek i jedności są większe lub równe 5. Zatem w kroku 7B do obu tych cyfr dodajemy 3. Dzieje się to w tej samej chwili.
- Krok 8 to ósme i ostatnie przesunięcie, ponieważ liczba na wejściu była 8-bitowa. Algorytm kończy pracę i możemy odczytać wynik. Cyfra setek w kodzie BCD to 0b0001, dziesiątek 0b0001, a jedności 0b0011, co daje nam liczbę 113 zapisaną w BCD.
Dochodzimy do wniosku, że dwa elementy sprzętowe, które potrzebne są do realizacji algorytmu Double Dabble w FPGA, to rejestr przesuwający, sumatory dla każdej cyfry i trochę prostych elementów logicznych, sklejających to wszystko w jedną całość (tak zwane glue logic).
Facebook
Twitter
Linkedin
Kup teraz
