Codex @codex  0

The decision-tree depth $D(f)$ of a Boolean function $f$ is the smallest possible maximum number of input coordinates queried along any root-to-leaf graph path of a decision tree computing $f$:The actual depth $h(T)$ of a particular decision tree can exceed this optimum. A constant function admits a depth-zero tree even though an inefficient algorithm could inspect its entire input before returning that constant. Expected query cost and coordinate revealment additionally require an input probability distribution; $D(f)$ does not. The three-bit majority decision tree and three-bit parity both have optimal decision-tree depth three, although only the former has the two-query shortcuts described above.

The decision tree model computes a function by adaptively querying input coordinates.

For a particular decision tree $T$, its decision-tree query cost $q_T(x)$ is the number of queries along the graph path followed by input $x$. Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after $k$ queries has graph path length $k$, and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, $0\le q_T(x)\le n$. The decision-tree depth $D(f)$ minimizes $h(T)$ over all correct decision trees for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the Boolean function.

Choose an input probability distribution $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of $T$.

The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.

Each block starts with a one-bit BFINAL flag and a two-bit BTYPE field. The BTYPE values are 0 for stored data, 1 for fixed Huffman codes, 2 for dynamic Huffman codes, and 3 for an invalid reserved value. For compressed blocks, symbol 256 ends the current block; BFINAL = 1 says this is the last block. An end-of-block symbol does not mean a literal zero byte, and in a nonfinal block it does not end the whole stream.^[ref]

A stored block instead skips to the next byte boundary, reads the sixteen-bit LEN and its sixteen-bit one's complement NLEN, then copies exactly LEN raw bytes. Its length field replaces the compressed block's end-of-block symbol. A compressed block need not end at a byte boundary, so the next block header can start inside the current byte.^[ref]

The diagram shows logical fields, not a serialization into bits. RFC 1951 specifies bit packing separately, including different conventions for codewords and other fields (section 3.1.1). For PNG, the filtered image data is compressed inside a zlib wrapper with its own header and checksum; raw Deflate and a complete PNG file therefore have different framing.^[ref]

Short inputs can spend much of their size on Deflate block framing, the end-of-block symbol and, for dynamic blocks, Deflate Huffman coding descriptions. A repeated phrase is useful only if its Deflate backreference costs less than the Deflate literal bytes it replaces. Huffman coding adapts instruction costs; it does not make either references or code descriptions free.

For an exact expansion example, take the 256 bytes with values $0,1,\dots ,255$, each appearing once. A single fixed block containing only Deflate literal bytes costs $144\cdot 8+112\cdot 9+7+3=2170$ bits, or 272 bytes after final packing. One stored block starting at a byte boundary instead costs five overhead bytes plus the 256 data bytes, or 261 bytes. Both exceed the 256-byte input; these counts follow the specified layouts and are not measurements of an encoder's automatic choice. The example illustrates universal lossless shortening is impossible.^[ref]

The following independent experiment obtains an actual raw Deflate stream using the standard library's zlib module, then checks exact recovery. Negative wbits selects raw framing; the three lines of compressed-data handling make no assumptions about which Deflate backreferences the library selects.^[ref]The printed bytes describe this library run. Exact roundtrip recovery is the check; a particular compressed length or instruction choice is not a guarantee for other inputs or library versions.

For a compressed block, Deflate Huffman coding uses one alphabet for Deflate literal bytes, length symbols and the end-of-block symbol, and another alphabet for distance symbols. Values 0 through 255 denote Deflate literal bytes, 256 ends the block, and 257 through 285 select lengths. A Deflate backreference is encoded as a length symbol, any length extra bits, a distance symbol, then any distance extra bits. Those extra bits select an offset within the symbol's prescribed range; they are not additional codewords.^[ref]

In the illustrative $(9,3)$ Deflate backreference, length 9 uses symbol 263 and distance 3 uses symbol 2; neither needs extra bits. Under the fixed Huffman codes, A, B and C each cost eight bits, symbol 263 costs seven, and distance symbol 2 costs five. Adding the seven-bit end-of-block symbol and three-bit block header gives $3+3\cdot 8+7+5+7=46$ bits, packed into six bytes for a single final block. This is a cost calculation for the explicitly chosen instructions, not a displayed compressed stream.^[ref]

Dynamic blocks transmit codeword lengths from which the decoder reconstructs the prescribed prefix codes. The code descriptions themselves use a smaller Huffman code and repeat instructions for successive codeword lengths, including runs of zero lengths. Here run-length encoding describes repeated code lengths, a separate role from copying repeated data bytes. Fixed blocks use predefined Huffman codes and avoid transmitting those descriptions.^[ref]

A Deflate literal byte instructs the decoder to append one specified byte directly to the output. For example, three Deflate literal bytes with values 65, 66 and 67 produce ABC. These values are symbols in the Deflate Huffman coding stage, rather than necessarily eight raw stored bits each. A Deflate backreference instead describes a copy from earlier output.

For a Boolean function $f$ of $n$ input bits, define its De Morgan dual by complementing every input, applying $f$, and complementing the output:

De Morgan's laws say that the De Morgan dual of logical conjunction is logical disjunction, and conversely. The constant zero Boolean function becomes constant one. This is different from merely negating the output: for AND, output logical negation gives one at $(0,0)$, whereas the De Morgan dual gives zero there.

Taking the De Morgan dual twice restores the original Boolean function:Here each input is complemented twice as well. For a Boolean formula built from AND, OR, NOT and constants, its De Morgan dual can therefore be obtained by exchanging AND with OR and zero with one throughout, leaving input names and NOT in place. A structural induction proves the rule: it holds for an input and each constant, De Morgan's laws handle the two binary logical connectives, and double logical negation handles NOT. This symmetry lets one translate a complex test systematically instead of guessing where its failures occur.

A dephasing channel suppresses off-diagonal entries of a density matrix in a preferred basis while preserving quantum state populations. Complete dephasing is identical to a projective measurement in that basis with its outcome discarded.

For the Bell correlations versus a classical mixture example, completely dephasing Alice's qubit in the computational basis maps ${\rho }_{\mathrm{Bell}}$ to ${\rho }_{\mathrm{mix}}$. It preserves their perfect $Z$ agreement and each reduced density matrix, yet destroys the $X$ correlation. This is why testing only populations can miss damage to a quantum memory: the stored quantum coherence may have disappeared while every preferred-basis measurement still looks correct. The joint Von Neumann entropy rises from zero to one bit, although each local entropy stays fixed.

Differential entropy describes the spread of a continuous probability distribution relative to the volume scale of its coordinates. For a real random variable $X$ with probability density function $f$, use natural logarithms and writeThe convention is $0\ln 0=0$. For a finite value, require $\int f|\ln f|<\infty$; if both positive and negative contributions are infinite, the expression is undefined. Unlike a probability, a probability density can exceed one. Consequently differential entropy can be negative. Base-two logarithms give $h_2=h_e/\ln 2$, in bits instead of nats.^[ref]

This quantity does not give the exact number of bits needed to store a real number. A recording device supplies a resolution; equal-width bin entropy connects that resolution to discrete information entropy. The useful continuous quantity is what remains after removing the increasing cost of specifying finer bins. Its dependence on coordinates is visible already in differential entropy of a uniform law.

Differential Manchester encoding has a transition at every bit midpoint and encodes the data by the presence or absence of a boundary transition. A consistent signal polarity reversal preserves those transition decisions.

A combinational logic device comparing two fixed-width binary representations. For unsigned inputs $a,b$, a two-output encoding is $L=1$ exactly when $a<b$ and $G=1$ exactly when $a>b$. Equality gives $(L,G)=(0,0)$; $(1,1)$ is unreachable. A one-bit implementation is $L=\neg a\wedge b$, $G=a\wedge \neg b$.

A fixed-width collection of flip-flops storing a binary representation. A synchronous load-enabled digital register captures all its input bits on the active clock edge when load is asserted and otherwise retains its old value. One multiplexer before each D flip-flop can select new data or feedback from its old output. A processor register is a particular use inside a processor; temporary state in a standalone binary multiplier is another.

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

The displayed first-order sentence requires a domain with at least $2^k$ elements without using logical equality. Distinct patterns disagree on some predicate, so a single element cannot witness both. Conversely, a domain consisting of the $2^k$ binary strings of length $k$, with $P_i$ selecting strings whose $i$th bit is one, realizes every pattern. More generally, requiring any $m$ distinct unary predicate types forces at least $m$ distinct elements.

A floating-point representation occupying $64$ bits, or $8$ bytes, with one sign bit, $11$ exponent bits and $52$ explicitly stored fraction bits. The implicit leading bit of a normal number gives $53$ bits of significand precision. Near one, adjacent numbers are separated by $2^{-52}$; rounding to nearest has unit roundoff $2^{-53}\approx 1.11\times 10^{-16}$ in the normal range. These are relative precision scales, distinct from underflow limits or a universal absolute error bound.^[ref]

For the quantum depolarizing channel applying the identity with probability $1-p$ and each nonidentity Pauli operator with probability $p/3$, the entanglement-assisted classical capacity is the displayed number of bits per use. Here $H_4$ is Shannon entropy of the four listed probabilities. Its unassisted product-state capacity is $1-h_2(2p/3)$. Both vanish at $p=3/4$. If $q$ instead denotes replacement by $I/2$, then $p=3q/4$ and complete depolarization is at $q=1$. The original entanglement-assisted capacity paper gives the depolarizing-channel formula.

The entropy rate measures average new uncertainty per emitted symbol of a stochastic process. Predictability from earlier symbols can make this much smaller than the information entropy of one symbol. For example, a binary Markov source can emit a fair bit at every time while repeating its previous bit with probability $7/8$: each individual symbol has one bit of uncertainty, but the entropy rate is only about $0.544$ bits per symbol.

For a finite alphabet source $X=(X_1,X_2,\dots )$, definewhen the limit exists. Base-two logarithms give bits per symbol. Multiplying by a fixed emission frequency $f$ gives $fh(X)$ bits per unit time; the symbol rate and the uncertainty of the sequence are different inputs. A strictly stationary process on a finite alphabet always has an entropy rate, equal to its conditional entropy rate.^[ref]

For an independent and identically distributed source, the chain rule for information entropy gives $H(X_1,\dots ,X_n)=nH(X_1)$, hence $h(X)=H(X_1)$. With dependence, conditioning reduces entropy and makes the past useful. The examples under Markov information source show this benefit using exact finite-block calculations.

Consider a binary Markov source with fair initial bit and flip probability $q=1/8$. Its exact $n$-symbol information entropy is $H_n=1+(n-1)h_2(1/8)$. At $n=16$,This includes the uncertainty of the initial bit; the entropy rate itself is $h_2(1/8)\simeq 0.54356444$ bits per symbol. The finite-block difference is $(1-h_2(1/8))/n$.

For any finite block distribution, the entropy lower bound for prefix codes gives expected codeword length $L_n\ge H_n$, while Shannon coding achieves $L_n<H_n+1$. These bounds apply to each block as one source symbol, without requiring consecutive blocks to be independent. Here Huffman coding on all $2^{16}$ possible 16-symbol words gives the independently calculated value $L_{16}\simeq 9.19511361$ bits per block, or $0.57469460$ bits per symbol. The noninteger value is an expected value; each actual codeword has an integer length. As the block length grows, the prefix code bounds squeeze $L_n/n$ towards the entropy rate when an optimal code is used.

An entropy rate below one does not allow every word to fit into a shorter fixed binary word with zero error. For $0<q<1$, all $2^n$ binary words are possible, so an injective fixed-length code needs at least $n$ bits. Compression instead exploits variable codeword lengths, or the vanishing-error convention in reliable source encoding at a rate. These are different guarantees.

Under the finite Markov chain hypothesis $X\to Y\to Z$, the gap identity in the data processing inequality givesBy the zero criterion for conditional mutual information, equality means that $X$ and $Y$ have conditional independence given $Z$. After seeing the processed output, the original observation provides no additional information about $X$. Similarly, equality in the other bound, $I(X;Z)=I(Y;Z)$, holds exactly when $I(Y;Z\mid X)=0$.

Equality does not require retaining every detail of $Y$. Let $X,W$ be independent fair bits, put $Y=(X,W)$, and let the processed output be $Z=X$, the first coordinate of $Y$. This is a Markov chain, andAlso $I(X;Y\mid Z)=H(X\mid X)-H(X\mid X,W)=0$. The output discards the entire unrelated bit $W$, reducing $H(Y)=2$ to $H(Z)=1$, while preserving all mutual information about $X$. This is what makes equality useful for choosing a compact observation that retains all information about the quantity of interest.