Умножение двоичных чисел 8-ми разрядным МК.

Автор: dr.doc
Опубликовано 02.11.2011
Создано при помощи КотоРед.

Здравствуйте, уважаемые!

Появление КотоРеда толкнуло меня на написание сего труда – написание алгоритмов и программ для математических операций умножения и деления двоичных чисел. Однажды столкнувшись с подобной проблемой, я решил просто помочь тем, на кого эти «действия», выложенные в интернете без подробного описания наводят благоговейный ужас. Итак: писал я на Ассемблере для PIC16, однако постараюсь донести саму суть и методику (одну из) для широкого понимания. На авторство решения я ни в коем случае не претендую, поэтому прошу не говорить про плагиат.

Умножение:

Для выполнения математических операций сложения и вычитания служит АЛУ – арифметико-логическое устройство, в число задач которого входит, помимо ненужных нам пока функций сложение с вычитанием. А так как перед нами стоит задача выполнять умножение, то остановимся подробнее на методике его выполнения. Умножение двоичных чисел производится также как и десятичных – в столбик. Пример показан на картинках ниже в десятичном и двоичном вариантах.

Если присмотреться внимательней, то можно увидеть, что множитель как бы сдвигается вправо и умножение каждый раз производится на самое правое его число (в примере двоичного умножения – нулевой бит регистра множителя). А так как в двоичной системе имеются только нули и единицы, то результатом умножения является либо множитель, либо нулевой регистр, следовательно пошаговое умножение можно заменить сложением с последующим сдвигом полученного числа!

Таким образом получаем следующую последовательность действий:

1. Так как количество суммирований равно числу бит множителя, занесем в регистр counter (произвольная переменная - счетчик проходов) число бит, в приведенном примере равное 8-ми.
2. Сдвигаем множитель вправо через бит carry (признак переноса). Если в carry логическая 1, то переходим к п. 5.
3. Суммируем средний байт (регистр) будущего ответа с младшим байтом (регистром) множимого, и если было переполнение (бит carry), то увеличиваем старший байт будущего ответа на 1. 
4. Суммируем старший байт (регистр) будущего ответа со старшим байтом (регистром) множимого.
5. Производим поочередный сдвиг вправо старшего регистра ответа, затем среднего и, наконец, младшего.
6. Уменьшаем счетчик бит counter на 1 с проверкой, закончились ли проходы? Если нет, то возвращаемся к п. 2.

После всех проведенных операций умножение закончено. В графическом виде алгоритм приведен ниже:

                   Графический алгоритм подпрограммы умножения.

Возможные вопросы:  почему производим сдвиг ответа вправо? Да потому, что первое число, полученное в результате умножения нужно сдвинуть именно вправо относительно последующего значения. Если это значение равно нулевому регистру, то производится простой сдвиг ответа вправо (переход с п. 2 на п. 5). Это можно хорошо рассмотреть на картинке с примером двоичного умножения выше на шагах 1-2-3-4.

Пример кода, написанный на Ассемблере для PIC16:

       MOVLW   0xAA

       MOVWF   BARGB0    ; множитель

;----------------------------------

       MOVLW   0xAA

       MOVWF   AARGB0    ; младший байт множимого

       MOVLW   0x55

       MOVWF   AARGB1    ; старший байт множимого

;----------------------------------

       CLRF    TEMPB0         ; младший байт ответа

       CLRF    TEMPB1         ; средний байт ответа

       CLRF    TEMPB2         ; старший байт ответа

       CALL    SMUL1608L

_1_

   GOTO    _1_                ; зацикливание для окончания счета и                  

                             ; проверки правильности работы программы

SMUL1608L                  ; подпрограмма умножения

       MOVLW   0x08          ; число проходов

       MOVWF   COUNT

LOOPSM1608

       RRF     BARGB0,F      ; сдвиг вправо множителя

       BTFSS   STATUS,C    ; в младшем разряде единица?

  GOTO    LSM1608NA

        MOVFW   AARGB0     ; младший байт множимого

        ADDWF   TEMPB1,F   ; складываем с средним байтом ответа

        BTFSC   STATUS,C     ; и, если произошло переполнение

        INCF    TEMPB2,F       ; увеличим старший байт ответа на 1

        MOVFW   AARGB1     ; старший байт множимого

        ADDWF   TEMPB2,F   ; складываем со старшим байтом ответа

LSM1608NA

        RRF     TEMPB2,F         ; поочередный сдвиг регистров ответа

        RRF     TEMPB1,F         ; вправо

        RRF     TEMPB0,F

        DECFSZ  COUNT, F        ; уменьшим число проходов на 1

        GOTO    LOOPSM1608   ; с проверкой на окончание

        RETLW   0         ; проходы вышли – выход из подпрограммы.

 END

   При наращивании разрядности, например 16*16 бит, число проходов counter должно равняться 16, а в ответе нужно предусмотреть еще один регистр, который нужно будет сдвигать самым последним, т.к. в приведенном алгоритме ответ сдвинется на 16 бит (2 регистра). Для упрощения приведу пример сложения двухбайтного числа:

1. Суммируем младший байт (регистр) 1-го слагаемого с младшим байтом (регистром) второго.
2. Если произошел перенос, увеличим на 1 старший байт второго слагаемого.
3. Суммируем старший байт (регистр) 1-го слагаемого со старшим байтом (регистром) второго.

Про деление двоичных чисел напишу немножко позже (спать охота), а пока разбирайтесь. Если чего-то не понятно, то вопросы в форум.

Все вопросы в Форум.