Two’s Complement Number wheel for 4 bit numbers
Download
Report
Transcript Two’s Complement Number wheel for 4 bit numbers
Two’s Complement
Number wheel for 4 bit
numbers
Addition
Subtraction
Booth’s Theory
00111110
25+24+23+22+21
26-21
• Looks for transitions from 0-1 (add)
and 1-0 (minus)
• Uses a “phoney” bit -1 (i.e. to the
right of bit 0)
• Assumes two’s complement signed
numbers
– extend bit width of unsigned numbers if
necessary.
Booths Algorithm
Two’s complement
multiplication examples
Division
CCS compiler w/ 2’s
complement
#device PIC16F877 *=8 ADC=8
void main()
{
signed int c;
c=-4;
}
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
3000
008A
2804
0000
0184
301F
0583
30FC
00A1
0063
MAIN
movlw
movwf
goto
nop
clrf
movlw
andwf
movlw
movwf
sleep
0x0
0xA
MAIN
0x4
0x1F
0x3
0xFC
0x21
Addition/Subtraction
#device PIC16F877 *=8 ADC=8
void main()
{
signed int c;
signed int b;
c=-4;
b=c+2;
}
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
000A
000B
3000
008A
2804
0000
0184
301F
0583
30FC
00A1
3002
0721
00A2
MAIN
movlw
movwf
goto
nop
clrf
movlw
andwf
movlw
movwf
movlw
addwf
movwf
0x0
0xA
MAIN
0x4
0x1F
0x3
0xFC
0x21
0x2
0x21,W
0x22
Done
Borrow
Subrgd
Addgood
datalo,W
resultlo,F
datahi,W
; W = Q1_hi - Q2_hi
; W = Q1_hi - Q2_hi
Q1_hi,W
R_hi
Done
Q1_hi,W
R_hi
R_hi,F
subwf
movwf
goto
subwf
movwf
decf
return
; do the decrement after
; need to borrow?
; W = Q1_lo - Q2_lo
; resulthi = resulthi + W
Q2_lo,W
Q1_lo,W
R_lo
Q2_hi,W
STATUS,C
Borrow
resulthi,W
resulthi
; If no carry ...
; if resulthi is 0 after the increment
; ... don't do the addition
; W = datalo
; resultlo = resultlo + W
; W = datahi
movf
subwf
movwf
movf
btfss
goto
addwf
movwf
btfsc STATUS,C
incfsz resulthi,F
movf
addwf
movf
Multiplication
&
Division
goto vs. call?
0063
0064
0065
0066
0067
0068
0069
006A
006B
006C
006D
006E
006F
0070
0071
0072
0073
0074
0075
0076
0184
301F
0583
30FA
00A1
0821
00A3
3005
00A4
2804
0878
00A2
0821
00A3
3003
00A4
283B
0878
00A2
0063
MAIN
#device PIC16F877 *=8 ADC=8
void main()
{
signed int c;
signed int b;
c=-6;
b=c*5;
b=c/3;
}
clrf
movlw
andwf
movlw
movwf
movf
movwf
movlw
movwf
goto
movf
movwf
movf
movwf
movlw
movwf
goto
movf
movwf
sleep
0x4
0x1F
0x3
0xFA
0x21
0x21,W
0x23
0x5
0x24
0x4
0x78,W
0x22
0x21,W
0x23
0x3
0x24
0x3B
0x78,W
0x22
Umul
; setup loop count
0x08
cntr
M1,W
M2,F
STATUS,C
R_hi,F
R_hi,F
R_lo,F
cntr,F
STATUS,Z
Umul
movlw
movwf
movf
rrf
btfsc
addwf
rrf
rrf
decf
btfss
goto
return
rotate into carry to check bits
if carry set i.e. bit was 1
... we add
shift over for the next addition
; check the loop count
;
;
;
;
; initialize W with M1
; Clear result location
R_hi
R_lo
clrf
clrf
; 8x8 unsigned multiply routine.
; No checks made for M1 or M2 equal to zero
CCS Compiler
Integer multiplication
• Repeated addition
–
–
–
–
store result sign
convert both integers to unsigned
store one integer in W
For each bit in integer;
• if set add W to the result
• rotate result
– if result sign is negative, convert
the result
BCD
• Decimal: Facilitates easy
conversion to/from human input
• BCD: Each digit represented by
an n-bit binary number
• Packed BCD: 2 digits
represented in a single byte
0
1
0
5
1
1
0
0
9
1
From: http://www.mindspring.com/~jc1/serial/Resources/ASCII.html
ASCII
• Visible Character Codes
• Control Codes
–
–
–
–
–
–
Physical Communication Control
Logical Communication Control
Physical Device Control
Physical Device Format Effects
Code Extenders
Information Separators
Floating point arithmetic
SBE ; B is known
X Y X S B X E YE YS BYE
X E YE
X Y X S B X E YE YS BYE
X Y X S YS B X E YE
X XS
X E YE
B
Y YS
CCS compiler floating
point numbers
CCS floating point
example
#device PIC16F877 *=8 ADC=8
void main()
{
float c;
c=1.25;
}
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
000A
000B
000C
000D
000E
3000
008A
2804
0000
0184
301F
0583
307F
00A1
3020
00A2
3000
00A3
00A4
0063
MAIN
movlw
movwf
goto
nop
clrf
movlw
andwf
movlw
movwf
movlw
movwf
movlw
movwf
movwf
sleep
0x0
0xA
MAIN
0x4
0x1F
0x3
0x7F
0x21
0x20
0x22
0x0
0x23
0x24
Should we use floating
point with the PIC?
• VERY LONG programs, which
are processor intensive
– try CCS assembler
float c=2.3;
c=2.3;
c=2.3*1.25;
• Possible Alternatives
– lookup tables
– fixed point representation
(factored arithmetic)
See:
http://www.phanderson.com/PIC/16C84/calc_disc_1.html
Memory Wars
•
•
•
•
Bit Numbering
Bit Ordering
Data Alignment
End-ian-ness
Changing bit-widths
• 2’s complement
– extend/reduce the sign bit
• BCD
– fill with 0’s at front
• ASCII
– defined as 7-bit
• Floating point
– fill significand (mantissa) at end
– add the change in offset to
exponent
Assembler Programming
Directives, Good Practice
• LIST p=<target microcontroller>
• #include <file>
– predefined constants for target microcontroller
• <const> EQU <value>
– define own constants (can be used for the
addresses of variables)
•
•
•
•
Labels in the first column
nop at address 0x00 (ICD)
goto at address 0x01 (Interrupts)
ORG <addr>
– next code line appears at this address
• BANKSEL <addr>
– switch banks to that for the specified address
• sleep at the end of the main routine
– Be careful that main code does not
“accidentally” run into subroutine code and vice
versa
• END -- end of the code
Table Creation/Lookup
table
addwf
retlw
retlw
retlw
retlw
end
PCL, F
B'00000001'
B'00000011'
B'00000110'
B'00000010'
DT “Bat”,0
;
;
;
;
;
add W and store in
return 1 in W if W
return 3 in W if W
return 6 in W if W
return 2 in W if W
retlw
retlw
retlw
retlw
A’B’
A’a’
A’t’
0
PCL
= 1
= 2
= 3
= 4
Table Creation/Lookup
BSF STATUS, RP1
BCF STATUS, RP0
MOVF ADDR, W
MOVWF EEADR
BSF STATUS, RP0
BCF EECON1, EEPGD
BSF EECON1, RD
BCF STATUS, RP0
MOVF EEDATA, W
DE (8-bit
;
;Bank 2
;Write address
;to read from
;Bank 3
;Point to Data memory
;Start read operation
;Bank 2
;W = EEDATA
data in the EEPROM memory)
ORG 0x02100
DE “Bat”,0
Table Creation/Lookup
BSF STATUS, RP1
BCF STATUS, RP0
MOVF ADDRL, W
MOVWF EEADR
MOVF ADDRH,W
MOVWF EEADRH
BSF STATUS, RP0
BSF EECON1, EEPGD
BSF EECON1, RD
NOP
NOP
BCF STATUS, RP0
MOVF EEDATA, W
MOVWF DATAL
MOVF EEDATH,W
MOVWF DATAH
;
;Bank 2
;Write the
;address bytes
;for the desired
;address to read
;Bank 3
;Point to Program memory
;Start read operation
;Required two NOPs
;
;Bank 2
;DATAL = EEDATA
;
;DATAH = EEDATH
;
DA
(14-bit data in the program memory)
ASCII strings packed two chars to a word
DA "abcdef"
will put 30E2 31E4 32E6 3380 into program memory
DA 0xFFFF
will put 0x3FFF into program memory
Page IV-6, Q.1
movf
btfsc
decf
decf
movf
btfsc
movf
Redundant
btfsc
goto
goto
countl,F
STATUS,Z
counth,F
countl,F
countl,F
STATUS,Z
count,F
s
STATUS,Z
Bz
Nbz
Original Code:
• 1 case: 2+8+2
• 216-1 cases: 2+9+2
• Avg. Cycles: 9
• Max. Cycles: 9
Modified Code:
• Remove 1 line
• Swap 2 lines
• 1 case: 2+8+2
• 216-1 cases: 2+7+2
• Avg. Cycles: 7
• Max. Cycles: 8
Page IV-6, Q.1
Tutorial Group Solution
movlw
subwf
btfss
decfsz
btfss
goto
movf
btfss
goto
goto
1
countl,F
STATUS,C
counth,F
STATUS,Z
Nbz
counth,W
STATUS,Z
Nbz
Bz
Subtraction of 1 can never result
in both a borrow and a zero result
i.e. if the carry flag is clear,
the zero flag is never set.
Early Exit
• C, Z 256 cases: 2+5+2
• C, Z
256*254 cases:
2+5+2
Remaining C, Z
• 255 cases 2+8+2
• 1 case: 2+9+2
• Avg. Cycles: 5
• Max. Cycles: 9
Tutorial Group page IV-6 Q. 6
To divide an x-bit dividend by a q-bit
divisor using Booth’s like division
– make an (q+x) bit number for the q-bit
remainder and x-bit quotient
– initialise the uppermost q-bits with the
sign bit of the dividend, and the lower
x-bits with the dividend
– Loop for x times:
• arithmetic left shift the (q+x) bit number
• if the sign is the same as(different from) the
divisor
– subtract(add) the divisor from(to) the
uppermost q bits
– if the result sign is different from the
original sign; undo
– if the result sign is the same as the original
sign OR the whole (q+x) number is 0; set
the LSB of the (q+x) bit number to 1
– Remainder is top q-bits. If the divisor
and dividend signs are same (different),
the answer is the (complement of )
bottom x-bits