Video 43 of 53 · 4:30 · Recognition and exact verification
The exact source-ANF core
In this video
Caption transcript
Show transcript
This overview explains how a packed
algebraic-normal-form representation stores exact coefficients and supports further representation comparisons.
Compact coefficient storage is not the same object as a packed truth vector and does not guarantee a universal runtime win.
In this algebraic normal form, multiplication means and and addition means exclusive-or.
The formula is A exclusive-or A B.
A term appearing twice would cancel.
These operations differ from ordinary real-number addition and
multiplication when values are combined.
At zero zero and zero one, A is zero, so both terms are zero.
At one zero, the A term is one and the product is zero, giving one.
At one one, both terms are one and cancel to zero.
The truth outputs are zero zero one zero.
In the declared monomial order, the constant coefficient is zero, A is present, B alone is
absent, and A B is present.
The coefficient sequence is zero one zero one.
It is not the truth-output sequence.
Algebraic normal form writes a Boolean function as exclusive-or of products.
A packed exact source-ANF representation stores coefficients while preserving the function.
C6 advanced this exact core; C7 and C8 tested identities and representations on another family and machine.
F is the exclusive-or of A and the product A AND B.
Its ANF has coefficient one on the terms A and AB.
On ascending A-B assignments its outputs are 0, 0, 1, 0.
The declared monomial order assigns the two nonzero coefficients to positions one and three.
Evaluating that stored ANF reconstructs the truth outputs.
This is coefficient packing, not packing the truth-output column; the two bit layouts represent different objects.
The retained C6 core advance did not automatically promote its gate or production path.
C7 and C8 retained exact identities while relative cost of set,
packed and bitset representations remained workload and machine dependent.
Preserve that distinction when the coefficient animation looks compact.
Work a second complete case with A 1, B 1.
Keep this assignment fixed throughout the calculation.
Each symbol retains the meaning already introduced; a new value does not
create a new logical rule.
The linear term contributes one.
The product term also contributes one because both of its inputs are one.
Over the two-element field, exclusive-or of these contributions is zero.
Adding them as ordinary integers would give two, which is not
this Boolean polynomial evaluation.
This case establishes a specific contrast.
GF(2) sum is XOR.
Coefficient storage and evaluation are distinct.
Keep the input, intermediate values, and conclusion together when comparing
it with the previous case.
The calculated answer belongs to this complete assignment under the stated rule.
Pack the coefficients with entry j in bit j.
Their weighted sum is ten, printed as binary one zero one zero.
Reading that numeral as a truth vector would attach the wrong meaning to its bits.
Pack the truth outputs by the same bit-position convention and obtain four, printed as
zero one zero zero.
The two words differ because one stores polynomial coefficients and
the other stores evaluated outputs.
A sparse coefficient form can be compact, but converting it or obtaining a requested full
vector still costs work.
A representation identity is not a benchmark result.
Compare complete matched tasks before deciding which storage or execution form is useful.
Declare whether bits index ANF terms or assignments.
Reconstruct exact outputs and keep representation costs tied to their workload and machine.

