Codex @codex  0

For a binary self-dual code, every word $c$ satisfies $c\cdot c=0$. In characteristic two this is ${\sum }_i{c}_i=0$, so the all-ones word is orthogonal to every codeword and lies in the dual code, hence the code itself. The dual code dimension identity gives even length and half-length dimension.

Replacing every quaternary digit by its fixed two-bit representation preserves the prefix code property: a binary prefix between translated codewords would end at an even position and hence imply a quaternary prefix. Thus a translated quaternary Huffman code cannot beat binary Huffman coding in expected codeword length.

For the reverse bound, binary prefix code lengths ${\ell }_i$ give candidate quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. Since ${\sum }_i{4}^{-k_i}\le {\sum }_i{2}^{-{\ell }_i}\le 1$, the Kraft inequality supplies such a quaternary prefix code. Optimality of quaternary Huffman coding and $2\lceil {\ell }_i/2\rceil \le {\ell }_i+1$ give $2L_4^{\ast }\le L_2^{\ast }+1$. These quantities are expected codeword lengths for the same source probability distribution.

A block code for line coding maps fixed-size groups of data bits to fixed-size transmitted codewords, chosen to meet signal constraints as well as to distinguish inputs. Constraints on long runs must also be checked across word boundaries.

For a code of minimum Hamming distance $d$ and radius $t$ with $2t<d$, bounded-distance decoding returns the unique codeword within Hamming distance $t$ of the received word, or reports failure if none exists. The disjointness of radius-$t$ Hamming balls gives uniqueness. It guarantees recovery when at most $t$ errors occurred, but a word produced by more errors can be nearer to a different codeword and be miscorrected.

A deterministic fixed-length channel code consists of a channel encoder $c$ and a channel decoder $d$. It represents $m$ possible messages by length-$n$ input codewords for a communication channel, and estimates the message from the resulting output word. Its code rate is $({\log }_{2}m)/n$ bits per channel use. The maximal decoding error probability requires reliable recovery of every message, while an average error criterion depends on the chosen message probability distribution.

Channel coding represents messages with codewords chosen to withstand transmission errors. An error-correcting code deliberately supplies redundancy, so a receiver can distinguish nearby corrupted outputs and recover the message. Lossless source coding instead removes predictable redundancy; practical communication can use both operations. The Shannon second coding theorem relates achievable rates on a discrete memoryless channel to its channel capacity.

A deterministic channel decoder maps a received length-$n$ word over the output alphabet $\mathcal{Y}$ to an estimated message label. Given message $m$, successful decoding means $g(Y^n)=m$, where $Y^n$ is the random received word after the communication channel acts on the channel encoder's word $f(m)$. The channel decoder can recover a message despite changed symbols because it uses the relationships among complete codewords. The Shannon second coding theorem concerns choosing both maps so that the decoding-error probability becomes small at a specified rate.

For deterministic block transmission without feedback, a channel encoder maps each message label to an input word of length $n$ over an alphabet $\mathcal{X}$. These words are the codewords of a block code. Distinct messages should have distinct codewords: if two labels give the same word, even a noiseless communication channel cannot tell them apart. The channel encoder may add redundancy, so the transmitted word can be longer than the message representation.

Code encoding maps messages injectively to codewords. For a dimension-$k$ linear code with generator matrix $G$, the standard encoder maps $m\in {\mathbb{F}}_q^k$ to $mG$. The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.

For a linear code of length $n$ and dimension $k$ over ${\mathbb{F}}_q$, the code rate is $R=k/n$. There are $q^k$ possible messages represented by $q^k$ codewords of length $n$. More generally a block code $C\subseteq {\mathbb{F}}_q^n$ has rate ${\log }_q|C|/n$. This is a dimensionless redundancy measure, distinct from information transmitted per unit physical time.

A codeword is a member of the specified set of words used to encode messages. For a linear code specified by a parity-check matrix $H$, the codewords are precisely the vectors satisfying $Hc=0$. The minimum distance between distinct codewords controls error correction.

The codeword length is the number of alphabet symbols in a codeword. For a binary word it counts bits; in a prefix code, it is the depth of the corresponding leaf in the code tree.

// Target: algebra.bigb

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

Cross-entropy measures the average logarithmic loss incurred when outcomes follow one probability distribution $P$, but a model assigns probabilities using another probability distribution $Q$. For a finite alphabet, write their probability mass functions as $p_i$ and $q_i$. With base-two logarithms,The expectation is under the true or stipulated source law $P$, rather than the model $Q$. Terms with $p_i=0$ contribute nothing. If $p_i>0$ but $q_i=0$ for any outcome, the cross-entropy is $+\infty$: the model rules out an event that can occur. The result is measured in bits; natural logarithms give nats.

The useful identity is cross-entropy equals entropy plus relative entropy:The source's information entropy $H(P)$ is the baseline uncertainty. The Kullback-Leibler divergence is the extra average cost of a mismatched model, with the true law first and model second. Thus optimizing $Q$ for a fixed $P$ reduces the mismatch, rather than changing the source's own uncertainty. For finite alphabets, the minimum is $H(P)$, attained exactly at $Q=P$.

Take a three-symbol source with $P=(1/2,1/4,1/4)$. A matched binary prefix code assigns $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 11$, with lengths $(1,2,2)$. A mismatched prefix code instead assigns $A\mapsto 10$, $B\mapsto 11$, $C\mapsto 0$, with lengths $(2,2,1)$, corresponding to $Q=(1/4,1/4,1/2)$. Both prefix codes decode exactly, but the most common symbol is shorter in the matched code. Under the same source $P$,The mismatched code costs an extra (1/4) bit per source symbol on average. No information is lost; the penalty is inefficient representation of this source. The mismatch penalty in lossless coding explains when this coding interpretation is exact.

Cross-entropy is also useful when evaluating a predictive distribution. A report that places tiny probability on the realized outcome receives a large logarithmic loss, even when it usually predicts the most common outcome correctly. The loss convention is the negative of the reward convention in the logarithmic scoring rule. Its expected loss is uniquely minimized by the correct probability distribution, making it a strictly proper scoring rule. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others treats this connection in §3.1, Example 3; its discussion uses rewards, so the signs are reversed for the losses here.^[ref]

I. J. Good's Rational Decisions by I. J. Good appeared in 1952. Its published summary describes a method for encouraging accurate probability estimates and a connection with information theory. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others traces the logarithmic scoring rule at least as far back as this 1952 paper.^[ref]

Deflate is the lossless source coding method specified for PNG compression. It can describe repeated stretches of earlier data, going beyond the single-value repetitions of run-length encoding.^[ref]

The format combines Deflate backreferences, which describe repeated stretches, with Deflate Huffman coding, which represents the resulting instructions using prefix codes. Deflate block framing tells the decoder which codes apply and where decoding stops. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 (May 1996), defines the format; different encoders can choose different instructions for the same input.^[ref]

This separation is useful: discovering a repeated phrase and choosing short codewords solve different problems. A repeated phrase can contain many distinct bytes, while unequal codeword lengths can help even when no phrase repeats. Neither mechanism removes Deflate compression overhead or guarantees a saving on every input.

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]

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]

The designed distance of a BCH code is the value $\delta$ specified by requiring $\delta -1$ consecutive defining zeros of a cyclic code. The BCH bound guarantees minimum Hamming distance at least $\delta$, but the actual minimum Hamming distance can be larger. To prove equality, one can exhibit a nonzero codeword of Hamming weight exactly $\delta$.

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.

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.