Skip to content
STIMSMITH

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

Concept

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.

First seen 7/28/2026
Last seen 7/28/2026
Evidence 4 chunks
Wiki v1

WIKI

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].

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections
Input and Output Generation for the Verification of ALU: a Use Case ← uses 95% 2e
The paper demonstrates the generation mechanism using addition with carry as a main example.
Arithmetic Logic Unit ← uses 90% 1e
The ALU supports addition with carry as one of its arithmetic operations.

LINKED ENTITIES

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

CITATIONS

13 sources
13 citations — click to expand
[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.