Algebraic normal form
From Wikipedia, the free encyclopedia
In boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula is considered to be in ANF if and only if it is a single algebraic sum (XOR) of one or more conjunctions of one or more literals. ANF is also known as “Zhegalkin polynomial” (Russian: полином Жегалкина) and as “Positive Polarity (or Parity) Reed-Muller” expression.
Putting a formula into ANF makes it easy to identify linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.
The general ANF can be written as:
 |
 |
 |
|
 |
|
 |
|
 |
where 
fully describes f.
[edit] See also
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
