Skip to content
STIMSMITH

Addition with Carry Operation (in Probabilistic Context-Free Grammar–Based ALU Verification)

Concept WIKI v1 · 7/28/2026

An addition with carry operation is an arithmetic operation supported by an arithmetic-logic unit (ALU) in which two N-bit operands A and B are summed bit by bit, with a carry bit propagated from the least significant bit to the most significant bit. In the context of automatic functional verification, this operation can be encoded as a probabilistic constrained context-free grammar whose production rules and constraints jointly generate valid input operands together with their expected sum, with the carry bit tracked through auxiliary non-terminals.

Addition with Carry Operation

Definition and Context

An addition with carry (ADD) operation is one of the arithmetic operations supported by an arithmetic-logic unit (ALU) considered in the paper "Input and Output Generation for the Verification of ALU: a Use Case" (IEEE EWDTS, Kazan, Russia, September 14–17, 2018). Together with subtraction (SUB), and the bitwise operations AND, OR, XOR, and NOT, it is one of the operations for which the authors generate input stimuli and matching expected output stimuli using a probabilistic constrained context-free grammar [1].

In the ALU model used, two N-bit operands A and B are fed to the ALU together with operation code OP, and the N-bit result R is produced. The ALU may have additional input/output bits such as status and control bits, but the paper restricts itself to the basic inputs and outputs [1].

Grammar Structure for Addition with Carry

To generate stimuli for addition with carry, the authors divide the process of creating production rules into three sections — Input values, Logic, and Result — each containing specific rules applied during generation. The Logic section is the most complex because its production rules must ensure the correct procedure for calculating the result [1].

Each operand is divided into N non-terminals (N is the operand bit width). For the 8-bit ALU case, operand A is split into bit non-terminals A7–A0 (A7 is the most significant bit, A0 the least significant bit), and the same is done for operand B [1].

The basic productions are:

  • A → A7 A6 A5 A4 A3 A2 A1 A0
  • B → B7 B6 B5 B4 B3 B2 B1 B0
  • Each bit non-terminal A7–A0 and B7–B0 can be replaced by either '0' or '1' [1].

After generating operand A from these productions, there is no information about carry propagation yet, because the carry bit is determined during the generation of operand B [2].

Carry Propagation via Context

To keep track of the carry and of the previously chosen bit of A, the authors extend each non-terminal Bi with the context of the corresponding bit of A. Hence each bit non-terminal B7–B0 can be replaced by [2]:

  • BiA0 — if Ai was zero,
  • BiA1 — if Ai was one,
  • BiA0C — if Ai was zero and a carry bit was set, or
  • BiA1C — if Ai was one and a carry bit was set.

For the very first (least significant) bit B0, there is no incoming carry, so the two production rules that would introduce a carry at the start of generation have their probabilities set to zero:

  • cons(->S, B0->B0A0C, 0);
  • cons(->S, B0->B0A1C, 0);

where S is the default starting non-terminal [3].

The context of the rule applied to A is stored in operand B, so the selection of rules for B and its corresponding bit is restricted. For each bit Ai, the productions that could otherwise put the wrong bit of A into the context are disabled (probability 0), e.g.:

  • cons(A0->'0', B0->B0A1, 0);
  • cons(A0->'0', B0->B0A1C, 0);
  • cons(A0->'1', B0->B0A0, 0);
  • cons(A0->'1', B0->B0A0C, 0);

and analogously for A7 [3].

After these restrictions, two rules remain for each bit B7–B1 that can be used after generating operand A, while B0 has only one deterministic rule without the carry bit. Once operand A and bit B0 have been generated, the carry bit for the following bit B1 and the result bit R0 can be determined [3]. The same logic applies to bits B2–B6 [3].

Result Generation

After operand A and operand B have been generated, the final result bits are produced. The result grammar is [2]:

  • R → R7 R6 R5 R4 R3 R2 R1 R0
  • R7, R6, …, R0 → '0', '1'

Constraints on rules BiA0C and BiA1C select the correct result bit. For example, for the least significant bit:

  • cons(B0A1->'0', R0->'1', 100);
  • cons(B0A1->'1', R0->'0', 100);

and similarly for B0A0:

  • cons(B0A0->'0', R0->'0', 100);
  • cons(B0A0->'1', R0->'1', 100); [3]

Truth Table (Grammar Truth Table of Addition with Carry C)

The selection of the result bit Ri and the outgoing carry Ci+1 for each combination of Ai and Bi follows the classical addition with carry truth table reproduced in the paper [a3eb191e-d311-45dc-9b08-6bfd7afc4748, b789ef68-a90f-43d3-bac0-3522056b481a]:

Ai Bi Ri Ci+1
0 0 0 0
0 1 1 0
0 0 (with C) 1 0
0 1 (with C) 0 1
1 0 1 0
1 1 0 1
1 0 (with C) 0 1
1 1 (with C) 1 1

In this table, "with C" denotes that the corresponding operand bit is generated through the BiA0C or BiA1C non-terminal, i.e., that an incoming carry is present [a3eb191e-d311-45dc-9b08-6bfd7afc4748, b789ef68-a90f-43d3-bac0-3522056b481a].

Worked Example

A concrete stimulus produced by this grammar is shown in the paper [2]:

  • OP (operation): 0
  • Operand A: 01101001
  • Operand B: 10001011
  • Result R: 11110100

The derivation order is: A0–A7, then B0–B7, then R0–R7 (rightmost non-terminals are substituted first), which guarantees that the carry context is available when each result bit is generated [a3eb191e-d311-45dc-9b08-6bfd7afc4748, b789ef68-a90f-43d3-bac0-3522056b481a].

Role in Verification

The probabilistic constrained grammar approach was introduced specifically to generate inputs and the matching expected output together, removing the need for a separate reference model when checking the ALU's functional correctness. The authors demonstrate the mechanism on the addition with carry operation, but note that the same principles are general and can be applied to other arithmetic or bitwise operations, to cyclic redundancy check generation, etc. [4].

The key insight is that the probability values of certain production rules are set to 0 or 100 to make the otherwise random grammar produce a valid, deterministic addition-with-carry result, while still allowing the operands to be varied randomly. This makes the "Universal Stimulus Generator" (USG) able to hit corner-case coverage points (such as all-ones or all-zeros in operands and result) faster than a plain random generator [4].

LINKED ENTITIES

2 links
Input and Output Generation for the Verification of ALU: a Use Case USES
Arithmetic Logic Unit USES

CITATIONS

13 sources
13 citations
[1] Addition with carry (ADD) is one of the arithmetic operations supported by the ALU examined, together with subtraction and the bitwise operations AND, OR, XOR and NOT. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[2] The ALU takes two N-bit operands A and B and an operation code OP, and produces an N-bit result R; in the paper the ALU uses 8-bit operands. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[3] Generation of stimuli for the addition-with-carry operation is split into Input values, Logic, and Result sections of production rules, with the Logic section being the most complex. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[4] Each operand is divided into N bit non-terminals (A7–A0 and B7–B0 for the 8-bit case) which can each be replaced by '0' or '1'. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[5] Because carry propagation is determined during generation of operand B, each non-terminal Bi is extended to carry the context of Ai and an optional incoming carry: BiA0, BiA1, BiA0C, BiA1C. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[6] B0 has no incoming carry, so the two productions that would start a carry at generation (B0->B0A0C and B0->B0A1C) are assigned probability 0 at the start symbol S. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[7] The context of Ai is stored in B by disabling productions that would mismatch Ai's value with the chosen context non-terminal (e.g., cons(A0->'0', B0->B0A1, 0), etc.). IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[8] After operand A and B0 are generated, the carry for B1 and the result R0 can be determined; the same pattern applies to bits B2–B6. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[9] The result non-terminals are R -> R7 R6 R5 R4 R3 R2 R1 R0, and constraints such as cons(B0A0->'0', R0->'0', 100) and cons(B0A1->'0', R0->'1', 100) make the result bits deterministic. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[10] Tab. 1 in the paper defines the classical addition-with-carry truth table for Ai, Bi, Ri, Ci+1 covering all eight combinations including those with an incoming carry. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[11] An example stimulus produced by the grammar is OP=0, A=01101001, B=10001011, R=11110100. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[12] The authors use the addition with carry operation as the demonstrator of their grammar-based input/output generation mechanism, and note that the same principles generalize to other arithmetic/bitwise operations and to CRC generation. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.
[13] By adjusting probability values, the Universal Stimulus Generator (USG) can hit corner cases (all-ones or all-zeros operands/results) faster than a purely random generator, improving code coverage in functional verification. IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 — Cekan et al.