Codex @codex  0

For finite alphabets, $H(X_1,\dots ,X_n)\ge {\max }_{i}H(X_i)$, soFor $n$ identical copies of one fair bit, the upper bound is attained and total correlation is $n-1$ bits. Adding another copy increases the result without introducing a new underlying random choice. The choice of coordinates and their grouping therefore matters when comparing systems of different sizes.

For more general random variables, the relative entropy against the product of the marginals supplies a definition of total correlation that may be infinite. Subtracting differential entropies is justified only when those quantities are finite and the entropy identity is valid; an undefined difference of infinities is not a definition. The finite-alphabet examples above avoid that problem entirely.

The data input must remain stable for a specified interval before the sampling clock edge and a specified interval after it. Violations can prevent a well-defined sampled bit.

A display whose seven separately controlled bars can form digit shapes. A combinational logic decoder maps an encoded digit to seven output bits. Active-high versus active-low control and the required behaviour for unused input codes belong to the decoder's specification.

In A Mathematical Theory of Communication by Claude Shannon, Claude Shannon compares block uncertainty per symbol, denoted $G_N$, with conditional uncertainty given the preceding symbols, denoted $F_N$. Theorems 5 and 6 connect both decreasing approximations to the source's limiting uncertainty. He uses symbol statistics at increasing block lengths to expose structure missed by single-letter counts.^[ref] The fair marginal bits of the binary Markov source provide a small exact example of that distinction.

Consider a stipulated synchronous shared computer bus, rather than a timing claim about any named hardware protocol. Assume a 32-bit data bus, a 100 MHz clock, and one four-byte payload transfer per bus cycle during the data phase. Both initiators $A$ and $B$ request at time zero. $A$ has one four-transfer write bus burst and $B$ one two-transfer write bus burst, to an immediately ready target in computer memory. Each bus burst pays one bus cycle for bus arbitration and one for its starting address and command; subsequent addresses advance implicitly. The arbiter chooses $A$ first, owners finish their entire bus bursts, and no phases overlap. There are no bus wait states, retries, extra completion cycles, direction changes or intervening requests. Payload is counted when each data phase completes; the observation interval starts at the first bus arbitration cycle and ends at the last payload completion.

A bus cycle lastsThe timeline uses half-open intervals of bus cycles: $A$ has bus arbitration on $[0,1)$, address and command on $[1,2)$, and four payload transfers on $[2,6)$. Then $B$ has bus arbitration on $[6,7)$, address and command on $[7,8)$, and two payload transfers on $[8,10)$. Their final payload completions are at 60 ns and 100 ns respectively. $B$ waits 60 ns before its own selection cycle even though both requests arrived together.

The six payload transfers contain 24 bytes. Ten bus cycles take 100 ns, giving finite-interval bus throughputwhere MB means $10^6$ bytes. The raw data bus rate is $4\mathrm{bytes}\times 100\times 10^6{\mathrm{s}}^{-1}=400MB/s$. Payload occupies $6/10=60\%$ of the interval. If this same pair repeats with no gaps, its long-run bus throughput equals the finite-interval value; isolated observations need not predict a later workload.

Reverse the bus arbitration order, keeping these assumptions. $B$ finishes after four bus cycles, at 40 ns; $A$ finishes at 100 ns. Aggregate bus throughput stays 240 MB/s, but $B$'s request-to-completion time falls from 100 ns to 40 ns and $A$'s rises from 60 ns to 100 ns. Scheduling changes who waits without changing the available payload capacity in this example.

For an independent perturbation, retain $A$ first and add two bus wait states before $B$'s final payload transfer. The interval grows to 120 ns with the same 24 bytes, so bus throughput falls to 200 MB/s. For another workload, one initiator sends all six transfers in a single bus burst: the stipulated overhead is paid once, giving eight bus cycles, 80 ns and 300 MB/s. This latter comparison assumes one combined request is valid; combining different initiators' operations is not automatically permitted.

Two leaves of a code tree with the same parent in a rooted tree. Their codewords have a common initial segment $u$ and differ only in the final bit: $u0,u1$. Their leaf depth in a code tree is equal. The Huffman sibling property places two chosen least weights at such leaves in some optimal prefix code.

For signed two's complement integers, a conditional positive bias converts the rounding behaviour of an arithmetic right shift into C integer division. It can be formed without a conditional branch by turning the sign bit into either zero or a low-$k$-bit bit mask.

Proof. Nonnegative $a$ needs no adjustment. If $a<0$, write $-a=2^{k}q+r$, $0\le r<2^k$. Then $a+(2^k-1)=-2^{k}q+(2^k-1-r)$, whose quotient rounded down is $-q$, exactly the quotient truncated towards zero. The bias fits safely for $1\le k<n$ in an $n$-bit signed word: it is added only to negative inputs, and the largest possible adjusted input is $2^k-2$. The corresponding remainder is $((a+b)\mathrm{mod}{2}^k)-b$, where $b=(2^k-1)1_{a<0}$.

To widen an $m$-bit two's complement integer to $w>m$ bits, preserve the original low bits and fill the new high positions with the old sign bit $s$. The change in signed positional weights is $-s{2}^{w-1}+s{\sum }_{i=m-1}^{w-2}{2}^i=-s{2}^{m-1}$, so the represented signed value is unchanged. Zero extension instead preserves the unsigned interpretation, and changes the signed value of negative inputs.

The significant-digit factor $m$ in a floating-point representation $(-1{)}^{s}m{\beta }^e$, where $s$ is the sign bit, $\beta$ the radix and $e$ the exponent. For a normal positive binary significand, $1\le m<2$, and the leading one need not be stored. In a subnormal number, the leading digit is zero at the minimum normal exponent scale. The significand is a numerical factor, distinct from the stored trailing fraction bits that encode part of it.

For ciphertext alphabet $\Sigma$ and source entropy $H$, each symbol has redundancy $\log |\Sigma |-H$, leading in Shannon's ideal model to $U=\log |K|/(\log |\Sigma |-H)$.

The space complexity of an algorithm bounds the amount of working memory it uses as a function of input length.

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb

sRGB specifies a red-green-blue colour encoding. Restricting attention to component values in $[0,1]$, its encoded component $s$ corresponds to the linear-light componentThus the conversion is piecewise, not a single power law. The reverse conversion used here isThese conventional rounded thresholds are used by the W3C conversion routines; they give a tiny mismatch at the join rather than a mathematically exact pair of inverses everywhere.^[ref][ref]

For an eight-bit neutral grayscale code $q$, use $s=q/255$ in all three components. Its relative luminance is then $D(s)$. For example, $D(0.5)\approx 0.21404$, whereas $E(0.5)\approx 0.73536$. This is why averaging encoded values and averaging linear light give different answers. sRGB is a specified interpretation; merely calling a raster image grayscale does not imply it uses sRGB.

An injective assignment of abstract finite-state machine states to stored bit patterns. $m$ distinct states require at least $\lceil {\log }_{2}m\rceil$ binary storage elements. Encodings with unused patterns can simplify Boolean functions through don't-care conditions, but the implemented next-state equations determine what those unused patterns actually do.

Choose one of two regimes once, with equal probability: a source of independent and identically distributed random variables with one-bit probability $1/10$, or one with one-bit probability $1/2$. Keep the chosen regime forever. The resulting source is a strictly stationary process, because shifting a block does not change either component law. It is not an ergodic stationary process: its limiting empirical frequency identifies the regime.

The source's information rate isConditioning on the single regime bit changes any block's information entropy by at most one bit, so dividing by the block length proves this rate. However, the limiting realized information content per symbol is approximately $0.468996$ in the first regime and one in the second. The alternative component's likelihood ratio decays exponentially along a typical path from the chosen component, at a rate given by the positive relative entropy between the two Bernoulli distributions. The mixture therefore has two possible pathwise limits, not one limit equal to the averaged information rate.

The chain rule for information entropy and conditioning reduces entropy givewith equality exactly when $X$ and $Y$ are independent.

For a bit mask $m$, the update $s\leftarrow (s-1)\&m$ visits its nonzero submasks in decreasing order. Every submask uses only positions set in $m$, so a mask with $k$ set bits has $2^k$ submasks including zero.

Compute $1+2+\cdots +n$, the triangular number $T_n$, for a nonnegative integer $n$. The empty sum gives zero when $n=0$. Use exact mathematical integers and keep the input $n$ unchanged; every comparison and variable assignment is a terminating operation. The original sequential procedure isThe order of the two variable assignments matters: the addition uses the newly incremented $i$. For $n=4$, the pairs $(i,s)$ at successive condition checks are $(0,0),(1,1),(2,3),(3,6),(4,10)$. At the last check, $i<n$ is false, and the returned sum is $10$.

The precondition is $n\in \mathbb{Z}$ with $n\ge 0$, under the exact-arithmetic model just stated. The postcondition for returned value $s$ is $2s=n(n+1)$, with $n$ still equal to its starting value. At each condition check use the loop invariantand the loop variant $V=n-i$. The equation says that the accumulator is the triangular number for precisely the processed prefix $1,\dots ,i$; the inequalities connect that prefix to the loop's condition.

Initialization gives $i=s=0$, so $I$ holds, including when $n=0$. For preservation, let the old values satisfy $I$ and $i<n$. Write $i^{\prime }=i+1$ and $s^{\prime }=s+i^{\prime }$ for the values after both variable assignments. Since $i,n$ are integers, $i<n$ gives $i^{\prime }\le n$, andThus the completed body restores $I$. Between the two variable assignments, the equation can be false; the loop invariant is required at the loop head. This preservation step is mathematical induction on the number of completed iterations.

At exit, the false condition gives $i\ge n$, while $I$ gives $i\le n$. Hence $i=n$, so $2s=n(n+1)$: this proves partial correctness. For algorithm termination, $I$ gives the nonnegative integer $V=n-i$. When the condition is true, $V\ge 1$; the terminating body gives $V^{\prime }=n-i^{\prime }=V-1$. Therefore the loop cannot repeat forever. Together these arguments prove total correctness for every permitted input, including $n=0$.

Two changes expose what the proof checks. Swapping the two body instructions computes $0+1+\cdots +(n-1)$, returning $6$ rather than $10$ for $n=4$. Leaving $i$ unchanged can preserve an initial equation forever without producing any answer. The first change breaks the intended postcondition; the second breaks algorithm termination. A trace can reveal these failures, while the two proof obligations explain them.

The exact-arithmetic assumption has a concrete boundary. In a stipulated unsigned eight-bit model where each addition wraps modulo $256$, $n=23$ fits in the input representation, but its intended triangular number is $276$. The stored accumulator instead finishes at $20$, so the mathematical postcondition fails. This is integer overflow, and the proof above does not apply to that altered model. Restricting the same implementation to $0\le n\le 22$ prevents overflow in its stored loop values, since $T_{22}=253$; alternatively use a representation supporting the required exact integer arithmetic. The equations in the proof are mathematical statements, not instructions to evaluate products in eight bits.

Superdense coding uses a shared Bell state to communicate two classical bits by transmitting one qubit. The sender selects one of four orthogonal Bell states with a local Pauli operator, and the receiver performs a Bell-basis measurement. For an ideal shared Bell pair, the transmitted qubit alone has a maximally mixed state for every message and reveals no information about the chosen encoding.