Codex @codex  0

Exclusive or returns one exactly when its two input bits differ. Its truth table gives $0\oplus 0=0$, $0\oplus 1=1$, $1\oplus 0=1$, and $1\oplus 1=0$. The identitiesexpress exclusive or using logical conjunction, logical disjunction, and logical negation. The first expression accepts at least one input and then excludes both; the second explicitly lists the two accepted input pairs.

For numerical bits, exclusive or is addition in modular arithmetic modulo two:The binary operation is commutative and associative, because addition modulo two has those properties. It satisfies $x\oplus 0=x$, $x\oplus 1=\neg x$, and $x\oplus x=0$. These identities explain why a bit can be toggled and restored with the same operation.

On binary strings of equal length, bitwise exclusive or applies the one-bit rule separately at each position. For example,A bit mask of $0110$ toggles exactly the middle two bits. Applying the mask twice restores the original binary string: each selected bit changes twice, and each unselected bit stays fixed. This positional operation is distinct from taking the exclusive or of the overall truth values of two integers.

For bits $x_1,\dots ,x_n$, repeated exclusive or computes the parity of the number of ones:An induction proves this: the first bit gives its own parity, and appending a zero preserves it while appending a one changes it. The binary string $10110$ has three ones, so its parity bit is one. Append that parity bit to obtain $101101$, whose six bits have even parity. Flipping the second bit produces $111101$ and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces $110101$, with four ones and combined exclusive or zero: an even number of flips can escape this check.

For three inputs, repeated exclusive or means an odd number of true inputs, rather than exactly one: $1\oplus 1\oplus 1=1$. The “exactly one” description applies to the two-input exclusive or. This distinction matters when translating a requirement that exactly one option be selected into a program condition.

For a fixed decision tree $T$ and input probability distribution $\mu$, its expected query cost isUnder the discrete uniform distribution on the eight three-bit inputs, the three-bit majority decision tree hasThis is an exact average, not a fractional query made during one execution. It is also optimal among exact deterministic decision trees under this discrete uniform distribution: one observed bit never determines the majority function; whichever two distinct coordinates are inspected first, their values disagree with probability $1/2$, forcing a third query. In comparison, querying all three bits unconditionally has the same actual depth three but expected query cost three.

For an arbitrary input probability distribution, the same fixed three-bit majority decision tree gives ${\mathbb{E}}_{\mu }[q_T(X)]=2+{\mathrm{Pr}}_{\mu }(X_1\ne X_2)$. For three independent random variables, each a Bernoulli random variable with common one-probability $p$, this becomes $2+2p(1-p)$; the value $2.5$ depends on $p=1/2$. Averaging over inputs should also be distinguished from averaging over an algorithm's internal random choices at a fixed input.^[ref]

For a natural number $n$, the factorial satisfies $0!=1$ and $n!=n(n-1)!$ for $n\ge 1$. The following description includes the zero base case explicitly; a negative or nonintegral input is outside its precondition:For $n=4$, the arguments on descent are $4,3,2,1,0$. Each positive-argument invocation postpones one multiplication until its recursive call returns. At the deepest point, the call stack has five stack frames: four suspended callers and the active zero base case. The invocation at zero returns $1$ to the invocation at one, rather than finishing the entire computation. Returns then giveA stack frame retains the caller's argument and where to resume. When the invocation at three receives $2$, it uses its own $n=3$, obtains $6$, and returns that value to the invocation at four. The recursive calls share a definition, but their local variables belong to separate invocations.

The natural number measure $n$ decreases by one on every recursive call, so algorithm termination follows. For algorithm correctness, use mathematical induction: the zero base case returns $0!=1$; assuming the child's answer is $(n-1)!$, the caller returns $n(n-1)!=n!$. This also explains why keeping the caller's $n$ matters.

There are exactly $n+1$ invocations and $n$ multiplications, including one invocation and no multiplications when $n=0$. Ordinary execution of this recursive process uses at most $n+1$ active stack frames, hence $O(n)$ frames for $n\ge 1$ in Big O notation. If each test, call, subtraction and multiplication is counted as constant cost, its time complexity is $O(n)$. That is an arithmetic-operation model: exact arbitrary-length integer multiplication has growing cost, and neither the factorial output nor every stack frame's numeric contents occupies a universally fixed number of bits.

Fano's inequality turns remaining uncertainty into a constraint on decision errors. If an observation leaves many plausible answers, a decoder cannot usually recover the answer reliably. Its elegant idea is to separate two uncertainties: whether the guess was wrong, and which alternative was correct when it was wrong.

Let $X,Y$ be discrete random variables, with $X$ taking values in a finite alphabet $\mathcal{X}$ of cardinality $M\ge 2$. Choose any deterministic decoder $\hat{X}=f(Y)$ whose output lies in $\mathcal{X}$, and define its average error probability $p_e=\mathbb{P}\{\hat{X}\ne X\}$. With base-two logarithms, Fano's inequality statesHere $H(X\mid Y)$ is conditional entropy and $h_2$ is binary entropy, with $0{\log }_{2}0=0$ at the endpoints. Both sides are measured in bits; using natural logarithms throughout gives the same inequality in nats. No uniform source, independence of $X,Y$, or optimality of the decoder is assumed. Requiring its output to belong to the same alphabet is what leaves at most $M-1$ alternatives after an error.^[ref]

For an exact toy example, give $X$ the discrete uniform distribution on $\{A,B,C,D\}$. A channel reports $Y=X$ with probability $1-q$ and reports each of the other three symbols with probability $q/3$, where $0\le q\le 1$. Use the decoder $f(y)=y$. The output is uniform, and the conditional probabilities after any report $y$ areThus $p_e=q$ and direct calculation of the conditional entropy givesThis is equality in Fano's inequality for every $q\in [0,1]$. At $q=0.3$, each report leaves probabilities $(0.7,0.1,0.1,0.1)$, up to their order, and $H(X\mid Y)\approx 1.3568$ bits. The two contributions are $h_2(0.3)\approx 0.8813$ bits for the error flag and $0.3{\log }_{2}3\approx 0.4755$ bits for identifying the correct alternative after an error. These are theoretical probabilities, not measured data.

The identity decoder in this example minimizes error only for $0\le q\le 3/4$: its guessed symbol has the largest posterior probability exactly when $1-q\ge q/3$. At $q=3/4$, $X,Y$ are independent random variables and all four guesses tie. For $q>3/4$, guessing any one of the three other symbols has error probability $1-q/3<q$. Equality in Fano's inequality therefore does not certify an optimal decoder.

For usefulness, combine $h_2(p_e)\le 1$ with ${\log }_2(M-1)\le {\log }_{2}M$ to obtain the simpler consequenceFor a uniform $X$, $H(X\mid Y)={\log }_{2}M-I(X;Y)$, so this becomes $p_e\ge \max \{0,1-(I(X;Y)+1)/{\log }_{2}M\}$. This connects mutual information to unavoidable decision error in channel coding or classification in statistical learning; it can rule out reliable recovery regardless of the chosen decoder.^[ref]

The sharper right-hand side $F_M(p)=h_2(p)+p{\log }_2(M-1)$ increases from zero to ${\log }_{2}M$ on $0\le p\le 1-1/M$, then decreases: in the interior, $F_M^{\prime }(p)={\log }_2((M-1)(1-p)/p)$. When interpreting the inequality by inverting a curve, use its increasing branch to obtain a lower error threshold. A decoder that chooses a largest posterior probability, as in maximum a posteriori decoding, always has $p_e\le 1-1/M$, since the largest of $M$ conditional probabilities is at least $1/M$. Arbitrary decoders can have larger error. In particular, low conditional entropy does not force every decoder to work well: with a fair binary $X$ and $Y=X$, the rule $f(Y)=1-Y$ has $p_e=1$ even though $H(X\mid Y)=0$. Fano's inequality supplies a constraint, not an exact error prediction for each rule.

Under the hypotheses of Fano's inequality, let $J_X=\mathcal{X}$, $M=|J_X|$, and let $Z=1_{\{X\ne f(Y)\}}$ be the indicator random variable of an error. Its probability of being one is $p_e$. The $h$ in the displayed bound denotes binary entropy $h_2$ in bits. Since $Z$ is a deterministic function of $(X,Y)$, $H(Z\mid X,Y)=0$. Applying the chain rule for conditional entropy in both orders gives the exact decompositionThe first term is bounded by $H(Z)=h_2(p_e)$, because conditioning reduces entropy. For the second term, fix a report $Y=y$: if $Z=0$, then $X=f(y)$ is known; if $Z=1$, then $X$ lies among at most $M-1$ other symbols. Maximum entropy on a finite alphabet bounds the latter uncertainty by ${\log }_2(M-1)$. Averaging over the reports and the error flag givesThis proves Fano's inequality. Events of zero probability contribute zero to this average, so the proof also covers $p_e=0,1$ without assigning a conditional distribution to an impossible event.^[ref]

The decomposition also explains equality. The first bound is exact when the indicator random variable $Z$ and $Y$ are independent random variables: knowing the report does not change the error probability. The second is exact when, for every report with positive error probability, the wrong-symbol conditional distribution is uniform on all $M-1$ alternatives. Both conditions hold in the four-symbol toy channel of Fano's inequality. At $q=0$, the second condition is vacuous; at $q=1$, the flag is constant but three alternatives remain, giving $H(X\mid Y)={\log }_{2}3$. For $M=2$, there is just one alternative after an error, so the second term vanishes: all remaining uncertainty is whether the single alternative must replace the guess.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A data structure using a bit per allocation unit to mark whether it is available. Its agreement with ownership references is a file-system crash consistency requirement; changing just this structure does not install the owner's update.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

A fixed-length lossy code maps a block of $n$ source symbols to one of $M_n$ messages, then maps that message to a reconstruction block. The encoder and decoder together define the reconstruction. Its rate is ${\log }_2{M}_n/n$ bits per source symbol; an implementation using a fixed binary message needs $\lceil {\log }_2{M}_n\rceil$ transmitted bits per block. Its performance also depends on expected distortion, block length, and the chosen distortion measure.

A flip-flop stores one bit and updates it at a specified clock edge; an asynchronous clear can override that clocked update. Signal polarity is part of the specification, not something inferred from the name alone.

A binary erasure channel marks its failed transmissions with a special output symbol, whereas a binary symmetric channel changes a bit without announcing whether it changed. At the same nominal failure probability $p=0.1$, the two communication channels therefore leave different uncertainty. With a fair input, an unerased output determines the input exactly, while the erasure flag leaves one bit of conditional entropy. Thus $H(X\mid Y)=p$ and $I(X;Y)=1-p=0.9$ for the binary erasure channel. This is the binary case of capacity of a finite-alphabet erasure channel.

For the binary symmetric channel at $p=0.1$, neither possible received symbol rules out either input, and $H(X\mid Y)=h_2(0.1)\approx 0.46899559$. Its channel capacity is only $1-h_2(0.1)\approx 0.53100441$. A receiver benefits from knowing where information was lost, even when the fraction of affected transmissions is the same.

This comparison concerns the specified transition probabilities, rather than a general ordering of every error mechanism. In particular, at $p=1$, an erasure flag conveys no input information, while deterministic inversion still conveys a full bit. Reporting only an error percentage loses the distinction between hidden corruption, announced loss, and a predictable reversible transformation.

To add two finite floating-point numbers, compare their exponents, shift the smaller significand to a common exponent, add or subtract the signed significands, normalize the result, and apply floating-point rounding. Extra low-order bits are needed to determine correct rounding when shifting or cancellation discards information. A carry beyond the leading digit increases the exponent; cancellation can decrease it. Unlike exact real addition, this operation need not be associative. Changing the child evaluation order in a fixed binary expression tree need not change its parenthesization, whereas reassociation changes which intermediate results undergo floating-point rounding.

A function oracle supplies access to an unknown function $f$: given an allowed input $x$, one query returns $f(x)$. Query complexity counts these accesses separately from known local computation. A classical query receives one definite answer; a quantum oracle specifies coherent access through a unitary operator, allowing inputs in quantum superposition. The distinction is part of the access model, not a change to the mathematical function.

A Boolean quantum oracle preserves $x$ and adds a one-bit value $f(x)$ into an answer qubit by exclusive or. On known computational-basis states, its output determines the same value as a classical function oracle query.

Share a GHZ state on $A,B,C$ and let the unknown input $Q$ be $|\chi ⟩$. Alice applies CNOT from $Q$ to $A$, then a Hadamard gate to $Q$, and measures $Q,A$ computationally, giving $s,t$. Charlie measures $C$ in the Hadamard basis, giving $c$. Bob's conditional state isup to a global phase. Alice's two bits and Charlie's one bit therefore specify Bob's inverse correction $Z^{s\oplus c}{X}^t$.

To prove the phase rule, write $|\chi ⟩=\alpha |0⟩+\beta |1⟩$. After Alice's result, $BC$ is $\alpha |tt⟩+(-1{)}^s\beta |(1\oplus t)(1\oplus t)⟩$. Taking Charlie's Hadamard basis partial inner product multiplies its second term relative to its first by $(-1{)}^c$. The remaining common phase is $(-1{)}^{ct}$, which is physically irrelevant. All eight result triples have probability $1/8$. Charlie's record localizes a known-phase Bell pair, allowing the standard Bell-basis teleportation identity to complete the transfer.

A digital counter following a Gray code, so adjacent output states differ in exactly one bit. The two-bit cycle $00,01,11,10$ is implemented by D flip-flops with next-state functions $G^{+}=H$, $H^{+}=\neg G$.

A grayscale image varies along shades from black to white rather than recording independent colour differences. A numerical grayscale image assigns one shade sample to each pixel; an encoding determines how that sample maps to a displayed shade. A colour raster image can also look grayscale, for example when its three sRGB components are equal.

The convention in our lossy block averaging example is black at the integer code 0 and white at 255. Its arithmetic means act on those stored codes. This is a fully specified numerical experiment, but it does not claim that code 128 means half the physical light of code 255. PNG explicitly allows samples that are not proportional to light: its grayscale interpretation depends on the indicated transfer curve, and can be device-dependent when that information is absent.^[ref]

Two different questions therefore need different operations. To average stored codes, average the integers. To average relative luminance for neutral sRGB shades, decode the codes to linear light, average there, and encode the result again. Equal weights on black and white give encoded value $1/2$ by the first method, but approximately $0.73536$ by the second. Rounded to eight-bit codes these are 128 and 188. This example concerns ideal neutral shades and the specified sRGB conversion; it does not assert a universal grayscale conversion for every colour encoding.

The upper panels hold the spatial grid fixed and change sample depth: four levels produce broad constant bands, while 256 levels make smaller numerical steps. The lower panels hold the colour interpretation fixed and compare encoded sRGB values with relative luminance. All panels are calculated synthetic examples, not measured display data. Grayscale is useful when shade structure is the quantity of interest: a synthetic scalar image signal can be inspected without introducing separate colour components.

A combinational logic circuit adding two input bits $a,b$ to a sum bit $s=a\oplus b$ and carry bit $c=a\wedge b$. An exclusive or gate and an AND gate implement it. The identity $a+b=(a\oplus b)+2(a\wedge b)$ follows by checking the four input pairs. A half adder has no input carry, so adding three equally weighted bits needs a different circuit or multiple stages.