The Characteristic Equations of the Digital Integrator

This is an English translation of the original German-language article “Die Funktionsgleichungen des digitalen Integrators” by W. Zoberbier (1968).

Abstract

The paper attempts to present the characteristic equations of the digital integrator in a form that allows a simple statement of the requirements for the integration unit for the programming of a general-purpose computer for rapid simulation. In addition, foundations are given for the synthesis of the critical circuit structure around the digital integrator.

1. Introduction

The digital integrator, as the characteristic component of the digital differential analyzer (DDA), uses the concept of “integration” in a computing sense. As input, it receives a sequence of increments Δx, in which the incremented variable x is encoded, and it supplies as output a sequence of increments Δy in which the integrated variable y is encoded. Formally, this is:

Input: a sequence of increments Δx₁, Δx₂, Δx₃, … encoding variable x
Output: a sequence of increments Δy₁, Δy₂, Δy₃, … encoding variable y

The digital integrator uses the concept of “integration” in the sense that:

y = ∫ z dx

where z is a second input variable (the integrand).

There are two forms of the digital integrator. In the first form, the integrand z is held constant during one iteration step and then forms the increment Δy for the corresponding step. In the second form (a more general Δy), the increment for each step is proportional to the product of z and Δx for that step.

2. The Operations of the Y-Operator (Y-Operatoren)

The digital integrator essentially integrates over all iterations. In abbreviated notation, it calculates:

Y = ∫ Z · DX

where Z is the integrand, X is the integration variable, and Y is the integral.

The fundamental register structure of the digital integrator consists of:

The Y-register holding the current integral value
The DY-register holding the output increments
The Z-register (or R-register) holding the current integrand value

The operational equations in the Y-register domain are derived from the step-wise accumulation process. For each iteration:

Y[n+1] = Y[n] + Z[n] · DX[n]
DY[n] = floor(Y[n+1]) - floor(Y[n])

where floor() indicates the integer part (truncation to the nearest lower integer).

2.1 Description via Y-Operator

The Y-operator is defined so that it maps the inputs Z and DX to outputs DY and (optionally) an overflow indicator. This requires careful treatment of the register boundaries.

The characteristic equations capture the behavior in terms of:

VY — the value stored in the Y-register
VZ (or VR) — the value stored in the Z/R-register
VDX — the input increment
VDY — the output increment

The iteration equation becomes:

VY[n+1] = VY[n] + VZ · VDX

with output:

VDY = VY[n+1] - VY[n] (integer part only, remainder stays in Y)

2.2 The Description via Z-Operator

When the integrator is run in the Z-operator mode (used for function generation and related tasks), the roles of the registers shift. In this case the Z-register is incremented:

VZ[n+1] = VZ[n] + DZ[n]

and the output:

VDY = VZ · DX (taken for each iteration)

This mode is particularly useful in simulation when computing z as a function of x.

3. The Operations of the Z-Operator

For the Z-operator, the integrator essentially forms running sums of the integrand. The characteristic equation governing the Z-operator is:

ΔZ_out = ΔZ_in (pass-through)

with the register update:

VZ[n+1] = VZ[n] + VDZ[n]

and overflow/underflow handling analogous to the Y-operator.

The boundary conditions (register overflow) are a central concern in both operator modes. The paper derives conditions under which the integration remains bounded and the overflow events correspond correctly to the mathematically expected increment outputs.

3.1 The Multivalue Approach for the Z-Register

The paper discusses a multivalue notation for describing the Z-register state, showing that the binary representation requires careful bookkeeping of carries and borrows during the summation.

4. The Synthesis of the Critical Circuit Structure

This section presents the foundations for synthesizing the circuit surrounding the digital integrator. Key results include:

Register boundary detection: The circuit must detect when VY crosses an integer boundary (either upward or downward) to generate DY = +1 or DY = -1 respectively.

Sign handling: The equations generalize to signed integers, where negative increments correspond to subtraction in the Y-register.

Overflow suppression: In practical implementations, the upper bits of VY that cause overflow must be handled carefully to avoid erroneous DY outputs.

The synthesis rules derived are:

For positive DX: DY = +1 whenever VY overflows upward
For negative DX: DY = -1 whenever VY underflows
The carry/borrow out of the most significant bit of VY is the DY output

These rules lead directly to the implementation in terms of binary adder circuits with carry detection.

4.1 The Binary DDA Integrator Cell

The paper derives the logic equations for a single DDA integrator cell operating on n-bit registers. The cell consists of:

An n-bit accumulator register Y
An n-bit Z/R register
Carry logic for DY output generation
Control logic for DX gating

The characteristic equations of this cell match the general formulas derived in earlier sections, confirming the consistency of the approach.

5. Minimization of the Y-Register

An important practical consideration is the minimum required word length for the Y-register. The paper shows that:

If VZ is bounded by |VZ| ≤ 2^(k-1), then the Y-register needs at most n = k bits (where k includes the sign bit)
For simulation purposes, the Y-register word length directly determines the precision of the integration

The minimization analysis also shows that shorter Y-registers increase the probability of spurious overflow events, so a balance must be struck between memory economy and numerical accuracy.

6. The Multivalue Notation for the Z-Register

A formal multivalue (Mehrwert) notation is introduced to describe situations where the Z-register state does not uniquely determine the output. This arises when VZ is exactly at a boundary value, and the DY output depends on the history (whether the boundary was approached from above or below).

The paper formalizes this using a function:

F(VZ) = {0, 1} when VZ is at a boundary F(VZ) = {floor(VZ)} otherwise

and shows that consistent behavior is achieved by making the DY rule:

DY = F(VY + VZ · DX) − F(VY)

which is well-defined except at the isolated boundary cases.

7. Considerations for the General-Purpose Computer Implementation

The final section applies the theoretical framework to the practical problem of implementing digital integration on a general-purpose computer for rapid (real-time) simulation. Key points:

The digital integrator’s equations map directly onto integer arithmetic instructions available on most computers
The DY outputs can be accumulated in a separate register on the host computer
The iteration rate (number of DDA steps per second) is limited by the host computer’s instruction execution speed
For simulation of continuous systems, the ratio of the DDA iteration rate to the simulated time scale must be chosen to ensure adequate numerical accuracy

Performance Estimates

The paper provides estimates showing that a fast computer of the era (1968) with an instruction cycle time of ~1 μs could execute approximately 10⁵ to 10⁶ DDA integration steps per second, making real-time simulation of low-order systems feasible.

References

The article cites foundational works on digital differential analyzers (DDA) including works by Palevsky, Selfridge, and others on the mathematical theory of DDAs, as well as engineering papers on hardware implementation.

[Translation covers all 9 pages of the original article.]