3
\$\begingroup\$

img

I have tried hard but I don't understand how this algorithm is working.Please explain the flow chart.

\$DVF\$ is the divide overflow flip flop.

\$A_s\$ is the sign bit of \$A\$

\$B_s\$ is the sign bit of \$B\$

\$E\$ is the register that has a carry bit

Initially the XOR operation is carried out to check if the sign bits of two numbers is equal.

The dividend is \$A\$ and \$Q\$ and the divisor in \$B\$. The sign of the result is transferred into \$Q_s\$ to be part of quotient. \$SC\$ is the sequence counter.

I am unable to understand the sequence of operations . What happens after the carry bit is checked for 1 or 0 ?

\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

Flowcharts are often not a very precise way of indicating what hardware is doing, since flowcharts often imply the existence of a single execution process, whereas hardware often does many overlapping and simultaneous operations.

The portions of the diagram circled in red seem a bit odd. It seems odd to latch A with the value after subtracting B, and then re-add B. More natural would simply be to not bother latching the lower part of the subtraction result. I think the flowchart might be clearer if "named values" were separated into "registers" and "values", and each step either computed values or registers. Thus, for example, one could have something like (assuming 16-bit registers)

C:T[15..0] = (A[14..0]:Q[15]) + ~B-1
if (C or A[15])
  A[15..0] = (A[14..0]:Q[15])
  Q[15..1] = Q[14..0]
  Q[0] = 1
Else
  A[15..0] = T[15..0]
  Q[15..1] = Q[14..0]
  Q[0] = 0
Endif

Every step that updates registers would represent a system clock. Events that merely compute values would not require a clock edge, but would be processed asynchronously.

\$\endgroup\$
11
  • \$\begingroup\$ I'm not really sure about your proposal: it seems to be too hardware-dependent, while this flowchart is intended as an abstract way to implement the division. But I agree that subtracting and re-adding is silly. \$\endgroup\$
    – clabacchio
    Commented Feb 2, 2012 at 16:00
  • 1
    \$\begingroup\$ @clabacchio: Nearly all computers consist of latches interconnected by logic. In many cases, all latches are triggered by the same clock, though in some cases there are multiple clocks which fire in sequence (e.g. on the 6502, there are two clocks, so on every cycle all the latches operated by phi1 will operate, then those will hold their values while the latches operated by phi2 operate, etc.). In the software world, each step can only affect a tiny fraction of the system state, while everything else sits idle; in the hardware world, things are much more "parallel". \$\endgroup\$
    – supercat
    Commented Feb 2, 2012 at 16:22
  • \$\begingroup\$ While I wouldn't want to suggest that an introduction to hardware division should employ every possible optimization, I would think it helpful to consider the notion of identifying which operations can happen simultaneously on a clock step. \$\endgroup\$
    – supercat
    Commented Feb 2, 2012 at 16:24
  • \$\begingroup\$ What I mean is that a bitwise representation is quite specific, and also the pipelining can be implemented in many different ways; now I'm not so expert in divider architecture, but I know at least 3 different and many different adder and multiplier architectures. What I mean is that a step that you could see in a certain way, in an implementation is performed in a different (and often much less intuitive) way. \$\endgroup\$
    – clabacchio
    Commented Feb 2, 2012 at 16:26
  • \$\begingroup\$ The only things I'm really doing differently, 'bitwise', are combining the shift with the next addition (perhaps a slight over-complication from a teaching standpoint, but one which will massively increase speed) and being more explicit in my notation (e.g. instead of saying EA=whatever, say "E:A[15..0] = whatever"). In some contexts, XY means (X 'and' Y), and in others it might mean a register called XY. Using a punctuation mark to indicate stacking seems like a good idea. \$\endgroup\$
    – supercat
    Commented Feb 2, 2012 at 16:33
2
\$\begingroup\$

\$ EA \leftarrow A+{\neg B} + 1\$ is the 2-complement sum of A and B (absolute), that means that you are subtracting B from A. Then, if you have a carry bit it means that the result is negative, and |B| is bigger than |A|. Since probably the division is integer, you cannot divide a number for a bigger one and it returns an overflow, that probably should mean that the result is 0.

Otherwise, B is again summed to A (seems odd, it could save it in a register instead of subtracting and summing the same value), and then enters in a loop:

The division is calculated one bit at a time, so I think that the shift operation should be a shift right, so starting from the most significant bit of the quotient, it checks if the divisor is contained in the dividend.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.