Codex @codex  0

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.

Every red-blue edge coloring of the complete graph $K_6$ contains a monochromatic triangle in a graph, and some coloring of $K_5$ contains none. Together the five-cycle Ramsey coloring and six-vertex monochromatic triangle argument giveThe threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.

A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.

The small size makes exhaustive verification practical. The complete graph $K_5$ has $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ edges, giving $2^{10}=1024$ red-blue colorings of labeled vertices; exactly 12 have no monochromatic triangle in a graph. They are the choices of a red cycle graph of length five, whose blue complement graph is another five-cycle. The complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ triples in every coloring finds none without a monochromatic triangle in a graph; in fact the minimum number is two. These counts can be reproduced by assigning one bit to each unordered pair and testing whether the three bits of each triple agree. The monochromatic-triangle counting formula gives a separate explanation of the stronger minimum-two conclusion.

Let $P$ be a nonzero multivariate polynomial over a field $K$, with total degree at most $d\ge 0$. Choose a nonempty finite set $S\subseteq K$. For independent random variables $a_1,\dots ,a_n$, each with a uniform distribution on a finite set on $S$, the Schwartz-Zippel lemma givesNonzeroness is essential; the zero polynomial always evaluates to zero. The total degree sums exponents within each monomial, rather than taking their maximum: $x^2{y}^3+y$ has total degree five. The field need not be finite, but $S$ must be finite. The estimate reduces error only when $d/|S|<1$.^[ref]

The proof begins with the root bound for a polynomial. For several variables, write $P={\sum }_{j=0}^m{Q}_j(x_1,\dots ,x_{n-1})x_n^j$, with $Q_m\ne 0$. The total degree of $Q_m$ is at most $d-m$. By induction, $Q_m$ vanishes with probability at most $(d-m)/|S|$. Otherwise the remaining univariate polynomial has at most $m$ polynomial roots. Adding the two contributions gives $d/|S|$.^[ref]

The algorithm samples a point, performs exact polynomial evaluation, rejects the identity if the value is nonzero, and otherwise accepts. The lemma bounds false acceptance for every fixed nonzero input. For the polynomial identity testing over a finite field example, $G$ has $d=2$ and $|S|=5$, so its exact $2/5$ error attains the bound. Numerical near-zero values from floating-point arithmetic do not satisfy this exact algebraic contract. A polynomial-time algorithm claim additionally needs efficient sampling and evaluation, including the bit cost of representing and operating on field elements. Counting field operations alone does not establish that cost.

A randomized algorithm makes some choices using random bits.

For a fixed input, the random bits can change the path taken by a randomized algorithm, its output, or its running time. Specify the distribution of those choices and which guarantee is required: one-sided error permits mistakes of only one kind, whereas ZPP requires a correct answer and bounds the expected running time. Polynomial identity testing makes this distinction concrete: choosing different field elements changes whether a nonidentity is detected.

A uniform distribution on a finite set must be implemented faithfully. To choose uniformly from $\{0,1,2,3,4\}$ using fair independent bits, read three bits as a number from zero to seven, discard five through seven, and repeat until a permitted value appears. Each retained value has the same chance. Taking the three-bit number modulo five instead would give zero, one and two twice as many preimages as three and four, invalidating a calculation that assumes equal chances.

Raster graphics describe a picture by an array of pixels on a grid. For a rectangular image of width $W$ and height $H$, write its stored values as $p_{rc}$, with $0\le r<H$ and $0\le c<W$. A grayscale pixel can have one shade value; a colour pixel can have several component values. The grid specifies where values belong, while the encoding specifies what those values mean. A raster image therefore needs dimensions and an interpretation of its samples, not just a string of numbers.

The appealing feature is that pictures become explicit data: selecting a rectangle selects entries of an array; comparing two images compares their pixel values; image compression can exploit repeated or related values. Raster sampling and reconstruction explains why the stored grid and the displayed picture are different objects. A square drawn around a sample is one display convention, not a claim that the original scene consisted of little squares.

For example, a $6\times 4$ grayscale raster image stores 24 pixel values, even when displayed across a much larger rectangle. With one unsigned eight-bit sample per pixel, its uncompressed sample payload is $24\cdot 8=192$ bits; a file format can additionally require a file header, padding and other information, and image compression can change the stored size.

Enlarging that image can copy each pixel into a block through nearest-neighbor interpolation, or infer intermediate values through interpolation. Either procedure supplies a reconstruction rule; neither determines which unrecorded detail was present in the original. Vector graphics use a different representation, specifying geometric objects to be rendered onto a chosen grid. Re-rendering such a description and enlarging an existing raster image are different operations.

Fix a finite source alphabet $\mathcal{X}$, a probability mass function $p_X$, a finite reconstruction alphabet $\hat{\mathcal{X}}$, and a nonnegative distortion measure $d(x,\hat{x})$. The information rate-distortion function isThe source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most $D$. The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is $+\infty$.^[ref]

Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect bits is allowed, the binary rate-distortion function givesHere $h_2$ is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in $0.18872$ physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and expected distortion $1/4$.

Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.^[ref]

Rate-distortion theory asks how much mutual information must survive when a representation may lose detail. Lossy compression groups different inputs into one reconstruction; a distortion measure specifies which differences matter. The rate-distortion function then gives a quantitative tradeoff between allowed expected distortion and the required number of bits. A smaller file is useful only if its reconstruction retains the distinctions that the application needs.

A memory read through an address whose contents are fixed during ordinary operation. Used as a Boolean function lookup table, $a$ address bits select one of $2^a$ words, each holding $b$ output bits, so the logical table capacity is $2^{a}b$ bits. A finite-state machine can store its next-state function in such a table while separate flip-flops store the current state.

The reconstruction alphabet is the set of values that the decoder may output. It need not equal the source alphabet. A restricted reconstruction alphabet can prevent zero expected distortion, even if the representation is allowed arbitrarily many bits.

A computation that retains pending operations while further calls run, then completes those operations as results return. A recursive procedure can instead describe an iterative process: passing an updated accumulator onward may leave no arithmetic pending. Avoiding growing call stack storage in that case depends on the implementation. A fixed number of variables also does not imply fixed storage in bits when their integer values grow.^[ref]

A processor design using a relatively regular instruction repertoire and explicit restrictions on operand forms. Immediate constants may have limited encodings, so extracting low bits with two bit shifts can avoid constructing a large bit mask in a temporary processor register. The benefit depends on the actual instruction set. A compact example appears in the Thumb 16-bit instruction set quick reference by Arm, whose logical bitwise AND instruction uses a processor register operand while shifts accept small immediate counts.

A collection of indexed processor registers. Selecting one of $R$ registers requires at least $\lceil {\log }_{2}R\rceil$ bits in a register index field.

With channel feedback, resend each message bit through a binary erasure channel until a non-erased copy arrives, then move to the next bit. The channel decoder deletes erasure symbols, giving the message without error whenever transmission completes. For $q<1$, the waiting times have an independent and identically distributed geometric distribution with expectation $1/(1-q)$, so every finite message completes almost surely. The strong law of large numbers gives forward code rate $n/{\sum }_{j=1}^n{M}_j\to 1-q$, matching channel capacity. At $q=1$, transmission never completes. Independent erasure indicators, rather than independent message bits, are the essential hypothesis.

A binary repetition code represents one bit by repeating it $n$ times, using codewords $0^n$ and $1^n$. Their Hamming distance is $n$, and the code rate is $1/n$. For odd $n$, the majority function recovers the input whenever fewer than half the positions have flipped. Even $n$ allows a tied vote, so a decoder must specify how it handles that case.

For $n=3$, the received words $000,001,010,100$ decode to zero; $111,110,101,011$ decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.

If each position passes independently through a binary symmetric channel with crossover probability $q$, a decoded error requires at least two flips. The binomial distribution givesAt $q=0.1$, the uncoded error probability is $0.1$, while the three-bit code's decoded error probability is $0.028$. This improvement costs three transmitted bits per message bit. For $0<q<1/2$, $3q^2-2q^3<q$; for $q>1/2$, one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.

Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability $q$, repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.

A cascade in which an output transition of one flip-flop clocks the next. With positive-edge-triggered toggle stages and uncomplemented $Q$ connections, it decrements modulo $2^n$: a zero bit rises to one and propagates a borrow, while a one bit falls to zero and stops propagation. Ripple propagation takes time, so intermediate transient states are not the settled counter state.

An arbiter selects at most one asserted request, searching cyclically after the most recent successful recipient. After a grant it advances that remembered position. This implements circular priority among bits representing competing requests; it is distinct from assigning a fixed priority forever.

Store both the last recipient index $L$ and a current-grant valid bit $V$. With $k$ possible recipients, an idle period clears $V$ while preserving $L$. The Moore machine grants requester $j$ precisely when $V\wedge [L=j]$ holds. For $k>1$, its $k$ idle states are distinguishable by a subsequent pair of competing requests with different positions in the cyclic order; active states have distinct outputs. Thus all $2k$ states are distinguishable and $\lceil {\log }_2(2k)\rceil$ state bits suffice and are necessary for this output convention. A continuously asserted request receives a grant within $k$ decisions, because before that grant the cyclic scan cannot pass it to choose a later asserted request.

Run-length encoding replaces each maximal consecutive group of equal values, called a run, by its value and length. Decoding repeats each value the specified number of times. It is lossless source coding: no values are discarded. For a binary string, successive maximal runs alternate between 0 and 1, so storing the first bit and all run lengths is enough.

Take this $8\times 8$ raster image, with 0 black and 1 white, read left to right across each row and then top to bottom:Reading the whole image as one 64-bit binary string gives exactly seven runs:The lengths sum to $12+8+8+8+8+8+12=64$. Repeating the alternating values for these lengths and splitting after every eighth pixel reconstructs every displayed row exactly.

Here is a complete toy file format. Its file header is an eight-bit unsigned width, an eight-bit unsigned height, then a one-bit mode: 0 means raw pixels, 1 means run-length encoding. Fields are written most significant bit first; this profile accepts only width and height 8, so both decoders know to stop at 64 pixels. Raw mode contains 64 bits. RLE mode contains the initial bit, followed by seven-bit unsigned run lengths in the range 1 to 64. Zero and lengths above 64 are invalid; a decoder rejects a run that would exceed the remaining pixel count. It stops when the decoded lengths sum to 64, so no run-count field or end marker is needed.

For this image, the complete RLE serialization is:Spaces and vertical bars are explanatory separators, not stored characters. The seven-bit fields directly store the lengths; 64 would be 1000000. The payload costs $1+7\cdot 7=50$ bits, versus 64 raw bits. The 17-bit file header has the same size in either mode, giving complete sizes of 67 versus 81 bits. If packed into eight-bit units, append zero padding only at the end: the sizes become 72 versus 88 bits. These are sizes of this toy representation, not sizes of PNG files.

The field design matters. Restarting RLE on every row costs eight initial bits plus four bits per run when lengths are stored directly: three bits represent only 0 through 7, whereas a row can have length 8. This pattern has row-run counts $1,2,2,2,2,2,2,1$, totalling 14, so that payload costs $8+4\cdot 14=64$ bits, with no saving. Storing length minus one would instead fit lengths 1 through 8 into three bits, but is a different declared file format. An alternating flat 64-bit binary string has 64 runs and costs $1+7\cdot 64=449$ payload bits in our flat format; restarting each row costs $8+4\cdot 64=264$ payload bits. A one-run image costs only eight payload bits. These extremes explain when RLE is useful: long uninterrupted regions make short instructions, while frequent changes make instructions expensive.

Prefix codes of unequal lengths can replace fixed-width run lengths, provided the decoder knows the code and any necessary code description is counted. Run-length encoding names a technique, not one universal serialization. For a real implementation, Microsoft's bitmap documentation specifies BI_RLE8 with count and value fields plus special commands, rather than our initial-bit convention.^[ref]

The sample depth $b$ is the number of bits allocated to one stored sample. An unsigned $b$-bit integer has $2^b$ codes, $0,\dots ,2^b-1$. This is per component, not automatically per pixel: three eight-bit components require 24 payload bits per pixel. A raster image with $WH$ pixels and $k$ such components requires $WHkb$ payload bits before data compression, padding or a file header.

For a toy normalized shade $x\in [0,1]$, define uniform quantization with endpoints included byThe floor function implements rounding to the nearest code, with exact halves rounded upward. The reconstruction step is ${\delta }_b=1/(2^b-1)$, and $|{\hat{x}}_b-x|\le {\delta }_b/2$. For $b=2$, the levels are $0,1/3,2/3,1$; for $b=8$ they are $0,1/255,\dots ,1$. Increasing sample depth refines this value grid without changing the spatial grid. These levels are uniform in $x$; if $x$ is encoded sRGB, they are not uniform in relative luminance.

PNG uses a bit-depth field per sample or palette index. Its grayscale type without alpha permits 1, 2, 4, 8 or 16 bits per sample; its truecolour type permits 8 or 16 bits per component. These are format-specific restrictions, not a rule for every raster image.^[ref]