Już dawno miałem zamiar opisania algorytmu konwersji liczb binarnych (dowolnej długości) na postać znakową. Algorytm ten polega na cyklicznej (tyle razy, ile bitów ma cała liczba) realizacji operacji przesunięcia o jeden bit i wykonania w pewnych przypadkach korekcji. Wszystkie operacje (sprawdzenie, czy konieczna jest korekcja oraz sama korekcja) są realizowane na 4-bitowych tetradach. Jeżeli 4-bitowa zawartość jest większa lub równa 5, to do tej tetrady należy dodać liczbę 3 (to jest ta wspomniana korekcja). Po wykonaniu wymaganej liczby operacji przesunięcia, wejściowa liczba jest zapisana w kodzie BCD, czyli każde 4 bity reprezentuje kolejne cyfry liczby. Do przejścia na postać znakową, do każdej tetrady należy dodać 30 hex (kod znaku '0').
Do ilustracji algorytmu napisałem odpowiedniego PDF'a, gdyż opisanie tego samego w poście jest upierdliwe (a może nawet niemożliwe). W PDF'ie wyszarzenie symbolizuje podział na 4-bitowe tetrady. Kolorem zielonym zaznaczyłem wsuwające się w wyniku przesunięcia zera.
Rozwiązanie to stosowałem również w układach FPGA do konwersji binarnych zawartości różnych rejestrów na postać znakową na wyświetlacz.
Załącznik ilustrujący algorytm:
Algorytm konwersji liczb binarnych na postać znakową
Algorytm konwersji liczb binarnych na postać znakową
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse
Re: Algorytm konwersji liczb binarnych na postać znakową
ooo, no to ja podziękowała za ten materiał...więcej w Motce zaraz
______________________________________________ ____ ___ __ _ _ _ _
Kończysz tworzyć dopiero, gdy umierasz. (Marina Abramović)
Kończysz tworzyć dopiero, gdy umierasz. (Marina Abramović)
Re: Algorytm konwersji liczb binarnych na postać znakową
tasza pisze:ooo, no to ja podziękowała za ten materiał...więcej w Motce zaraz
Przeczytałem materiał w opcjach księżniczki motorolki i cieszę się, że stał się kamieniem milowym na Twej drodze
Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse
Re: Algorytm konwersji liczb binarnych na postać znakową
Algorytm jest pokłosiem arytmetyki BCD. W niektórych prockach występują specjalne instrukcje i wskaźniki przeznaczone do arytmetyki BCD. Przykładowo takie możliwości sprzętowe mają procki z rodziny C51.
Kod BCD (ang. Binary Coded Decimal czyli liczby dziesiętne zakodowane binarnie) pozwala zapisać w jednym bajcie dwucyfrową liczbę traktowaną w systemie dziesiętnym. Każda z cyfr zajmuje 4 bity. Wiadomo, że na 4 pozycjach bitowych można zapisać 16 różnych kombinacji, jednak w systemie dziesiętnym występuje 10 cyfr (jako cyfry od 0 do 9). Do zapisania każdej z cyfry dziesiętnej potrzeba również 4 bitów. Niewykorzystane kombinacje (cyfry od A hex do F hex) należy traktować jako nielegalne. Przykładowo zapisanie liczby 23 w kodzie BCD wygląda następująco:
Na starszej połówce mamy 0010 bin co odpowiada liczbie 2 dec, na dolnej połówce mamy 0011 bin co odpowiada 3 dec. Okazuje się, że na tak zapisanych liczbach można realizować operacje dodawania w tradycyjny sposób. Przykładowo:
Realizując typową operację dodawania binarnego (instrukcja ADD) uzyskuje się praktycznie poprawny wynik. Ze względu na “niepełne” wykorzystanie kombinacji binarnych w kodzie BCD w pewnych sytuacjach pojawiają się problemy. Rozpatrzmy następujący przykład:
Ponieważ w wyniku dodawania binarnego pojawia się liczba spoza zakresu liczb BCD (C hex), należy dokonać drobnej korekty. W sytuacji, gdy na młodszej pozycji pojawiła się cyfra spoza zakresu, do powstałego wyniku należy dodać liczbę 06 hex (w przypadku, gdy podobna sytuacja dotyczy starszej liczby BCD, należy do powstałego wyniku dodać 60 hex).
W wyniku korekty powstał poprawny wynik (15 dec+17 dec=32 dec).
Rozpatrzmy jeszcze jeden przykład:
W tym przypadku również należy dokonać odpowiedniej korekty otrzymanego wyniku (pomimo, że uzyskane cyfry BCD zawierają się we właściwym przedziale). Po dodaniu 06 hex uzyskany jest wynik 37 BCD. W tym przypadku wystąpiło przeniesienie z bitu numer 3 na bit numer 4. We wskaźnikach mikrokontrolerów z rodziny C51 znajduje się wskaźnik AC (ang Auxilliary Carry – wskaźnik przeniesienia pomocniczego). Ustawienie wskaźnika AC oznacza, że nastąpiło przeniesienie z młodszej cyfry BCD na starszą cyfrę BCD. Dość złożoną operację związaną z korektą (samo dodanie jest operacją prostą, jednak należy rozpatrzeć dość złożony warunek pozwalający zdecydować, czy dodanie jest konieczne) wykonuje instrukcja korekty dziesiętnej, instrukcja DA A. W przypadku, gdy nie jest wymagana korekta, instrukcja DA nie wykonuje żadnych operacji. Podsumowując, w przypadku realizacji dodawania (ADD) liczb zapisanych w kodzie BCD należy zawsze wykonać instrukcję korekty (DA). W pewnych przypadkach wykonanie tej instrukcji nie zmieni zawartości rejestru A, w innych zostania dokonana właściwa korekta.
Kod BCD (ang. Binary Coded Decimal czyli liczby dziesiętne zakodowane binarnie) pozwala zapisać w jednym bajcie dwucyfrową liczbę traktowaną w systemie dziesiętnym. Każda z cyfr zajmuje 4 bity. Wiadomo, że na 4 pozycjach bitowych można zapisać 16 różnych kombinacji, jednak w systemie dziesiętnym występuje 10 cyfr (jako cyfry od 0 do 9). Do zapisania każdej z cyfry dziesiętnej potrzeba również 4 bitów. Niewykorzystane kombinacje (cyfry od A hex do F hex) należy traktować jako nielegalne. Przykładowo zapisanie liczby 23 w kodzie BCD wygląda następująco:
Na starszej połówce mamy 0010 bin co odpowiada liczbie 2 dec, na dolnej połówce mamy 0011 bin co odpowiada 3 dec. Okazuje się, że na tak zapisanych liczbach można realizować operacje dodawania w tradycyjny sposób. Przykładowo:
Kod: Zaznacz cały
00010001 = 11 BCD
+ 00100010 = 22 BCD
-----------------------
00110011 = 33 BCDKod: Zaznacz cały
00010101 = 15 BCD
+ 00010111 = 17 BCD
-----------------------
00111100 = 2C binKod: Zaznacz cały
00010101 = 15 BCD
+ 00010111 = 17 BCD
-----------------------
00101100 = 2C bin
+ 00000110 = 06 bin
-----------------------
00110010 = 32 BCDW wyniku korekty powstał poprawny wynik (15 dec+17 dec=32 dec).
Rozpatrzmy jeszcze jeden przykład:
Kod: Zaznacz cały
00011001 = 19 BCD
+ 00011000 = 18 BCD
-----------------------
00110001 = 31 bin
+ 00000110 = 06 bin
-----------------------
00110111 = 37 BCDW tym przypadku również należy dokonać odpowiedniej korekty otrzymanego wyniku (pomimo, że uzyskane cyfry BCD zawierają się we właściwym przedziale). Po dodaniu 06 hex uzyskany jest wynik 37 BCD. W tym przypadku wystąpiło przeniesienie z bitu numer 3 na bit numer 4. We wskaźnikach mikrokontrolerów z rodziny C51 znajduje się wskaźnik AC (ang Auxilliary Carry – wskaźnik przeniesienia pomocniczego). Ustawienie wskaźnika AC oznacza, że nastąpiło przeniesienie z młodszej cyfry BCD na starszą cyfrę BCD. Dość złożoną operację związaną z korektą (samo dodanie jest operacją prostą, jednak należy rozpatrzeć dość złożony warunek pozwalający zdecydować, czy dodanie jest konieczne) wykonuje instrukcja korekty dziesiętnej, instrukcja DA A. W przypadku, gdy nie jest wymagana korekta, instrukcja DA nie wykonuje żadnych operacji. Podsumowując, w przypadku realizacji dodawania (ADD) liczb zapisanych w kodzie BCD należy zawsze wykonać instrukcję korekty (DA). W pewnych przypadkach wykonanie tej instrukcji nie zmieni zawartości rejestru A, w innych zostania dokonana właściwa korekta.
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse
Re: Algorytm konwersji liczb binarnych na postać znakową
No mnie to się to scrollowanie bitów spodobało więc tym sposobem dalej myślę.
To prawda, że są procesory wspierające operacje na BCD, ale jak nie ma, to trzeba sobie radzić domowymi sposobami i z użyciem prostackich instrukcji. Zatem poniżej dodawanie dwóch trzycyfrowych liczb w BCD ale bazujące na przesuwaniu w prawo kolejnych nibbli czy tetrad jak kto woli, fajny patent.
Operacja wykonywana jest na jednej parze cyfr BCD (w przykładzie są więc trzy takie akcje), jedna operacja atomowa to: dodanie cyferek do siebie binarnie (wraz z wartością przeniesienia w poprzedniego obiegu), jak wyjdzie > 9 to zapamiętanej tego faktu w wartości na przeniesienie (wartość w ramce) a następnie binarne dodanie do nibbla wyniku wartości 6. Mamy wypracowane 4 bity wyniku w BCD.
Potem trzeba cały majdan przesunąć o 4 bity (tetrade) w prawo, w miejsce wyniku zaczną jakby wpływać kolejne wartości, począwszy od najmłodszej cyfry
I ponownie to samo, sumujemy 0 lub 1 (gdy było przeniesienie) z kolejnym słupkiem , robimy korekcje i wsuwamy wynik.
Na przykładzie mym ten ostatni obieg to przypadek, który dodaje wartość korekcji z poprzedniego, ale sam jej nie generuje i szafka gra.
Aha, no i to w pętelce wykonując można uogólnić na N cyferek, czyli dodawać do siebie tasiemce, pamiętając tylko aby było miejsce na wynik (N+1 cyfr)
Wykorzystywane operacje procesora to elementarz shift, rotate right, and, add – no to każdy chyba ma, nawet jak o BCD nie słyszał,
To prawda, że są procesory wspierające operacje na BCD, ale jak nie ma, to trzeba sobie radzić domowymi sposobami i z użyciem prostackich instrukcji. Zatem poniżej dodawanie dwóch trzycyfrowych liczb w BCD ale bazujące na przesuwaniu w prawo kolejnych nibbli czy tetrad jak kto woli, fajny patent.
Operacja wykonywana jest na jednej parze cyfr BCD (w przykładzie są więc trzy takie akcje), jedna operacja atomowa to: dodanie cyferek do siebie binarnie (wraz z wartością przeniesienia w poprzedniego obiegu), jak wyjdzie > 9 to zapamiętanej tego faktu w wartości na przeniesienie (wartość w ramce) a następnie binarne dodanie do nibbla wyniku wartości 6. Mamy wypracowane 4 bity wyniku w BCD.
Potem trzeba cały majdan przesunąć o 4 bity (tetrade) w prawo, w miejsce wyniku zaczną jakby wpływać kolejne wartości, począwszy od najmłodszej cyfry
I ponownie to samo, sumujemy 0 lub 1 (gdy było przeniesienie) z kolejnym słupkiem , robimy korekcje i wsuwamy wynik.
Na przykładzie mym ten ostatni obieg to przypadek, który dodaje wartość korekcji z poprzedniego, ale sam jej nie generuje i szafka gra.
Aha, no i to w pętelce wykonując można uogólnić na N cyferek, czyli dodawać do siebie tasiemce, pamiętając tylko aby było miejsce na wynik (N+1 cyfr)
Wykorzystywane operacje procesora to elementarz shift, rotate right, and, add – no to każdy chyba ma, nawet jak o BCD nie słyszał,
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
______________________________________________ ____ ___ __ _ _ _ _
Kończysz tworzyć dopiero, gdy umierasz. (Marina Abramović)
Kończysz tworzyć dopiero, gdy umierasz. (Marina Abramović)
Re: Algorytm konwersji liczb binarnych na postać znakową
tasza pisze:są procesory wspierające operacje na BCD, ale jak nie ma, to trzeba sobie radzić
Święte słowa, jak widać, nie ma takiej dziury, której nie da się odetkać.
Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse
Kto jest online
Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 2 gości